377. Combination Sum IV

377. Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/

문제

풀이

위에 DP테이블은 Example1의 DP 테이블이다.
4일 때 경우를 보면 (3, 1), (2, 2), (1, 3)이 있는 것을 볼 수 있는데
(3, 1) => (3, 1) 1개
(2, 2) => (2, 2), (2, 1, 1) 2개
(1, 3) => (1, 3), (1, 2, 1), (1, 1, 2), (1, 1, 1, 1) 4개이다.
이것은 dp표에 저장된 dp[3][1] + dp[3][2] + dp[3][3] = 7을 한 값이다.
이것을 코드화 하면 다음과 같다.

target = 0일 때 즉 j == 0일 때에는 1로 초기화 해주고, nums[i-1] > j이라면(num[i-1]값이 5고 target 4라면 nums[i-1]값을 사용할 수 없다는 의미) 해당 nums값은 사용할 수 없으니 위에 dp값을 저장한다.

결과