혹시 냅색문제의 경우 dp를 1차원으로 해결 할 수 있는 방법은 없을까요?

public class BOJ_12865 { static int N; static int K; static int[][] merchandise; // 0 : 무게, 1 : 가치 static int[][] dp; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); K = sc.nextInt(); merchandise = new int[N][2]; dp = new int[10000000][N]; for (int i = 0; i < 10000000; i++) { for (int j = 0; j < N; j++) { dp[i][j] = -1; } } for (int i = 0; i < N; i++) { merchandise[i][0] = sc.nextInt(); merchandise[i][1] = sc.nextInt(); } int max = recursion(0, 0); System.out.println(max); } private static int recursion(int index, int weight) { if (weight > K) { return Integer.MIN_VALUE; } if (index == N) { return 0; } if (dp[weight][index] != -1) { return dp[weight][index]; } dp[weight][index] = Math.max(recursion(index + 1, weight), recursion(index + 1, weight + merchandise[index][0]) + merchandise[index][1]); return dp[weight][index]; }안녕하세요 덕분에 강의 잘 듣고 있는 수강생입니다. 냅색 문제를 풀고 있는데, 최대 가능한 무게의 경우 100 (배낭 물품의 최대 개수) * 100,000(각 물건의 최대 무게) 로 생각보다 생성해줘야하는 배열의 크기가 크더라구요. 그래서 혹시 dp를 1차원 배열로 생성하면 어떻게 되는 지 궁금하여 1차원 배열로 해본 결과, 무게를 고려하지 않고 dp의 무게 갱신을 하게 되어 답이랑은 다르게 나오네요. 혹시 1차원 배열을 시도하려고 할 때 제가 놓치고 있는 부분이 있을까요?감사합니다.