N차원 배열만으로는 문제풀이에 부족한 경우가 생긴다.
이럴 때 N+1차원 배열을 사용해 dp를 적용할 수 있는데.. 아무래도 N차원 dp보다는 생각하기 쉽지 않다.
핵심은 N차원으로는 해결할 수 없으니 이차원으로 메모리를 확장하는 부분이다.
확장한 메모리를 어떻게 사용할 지는 문제마다 다르니, 역시 많이 풀어서 감을 잡는게 중요하다.
https://www.acmicpc.net/problem/1495
boolean dp[i][j] = i번째 곡에서 j볼륨을 사용할 수 있는가?
https://www.acmicpc.net/problem/14852
빠른 계산을 위해 이차원 배열을 도입해서 이 전까지의 값을 저장한다.
https://www.acmicpc.net/problem/14722
dp[r][c][n] = r,c 좌표에서 n종류의 우유를 먹었을 때의 최대 수
https://www.acmicpc.net/problem/15989
dp[i][j] = 임의의 i를 구할 때 마지막이 j인 경우의 수