(DP, Medium) Combination Sum IV

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

Climbing Stairs의 심화버전 같은 문제다.

경우의 수가 nums만큼이 있으므로 이것을 계산해야 한다.

dp 배열은 다른 문제들과 같이 target+1 길이를 가지는 int배열로 만들어 주고, dp[target]을 통해 가능한 경우의 수를 뽑아낼 수 있도록 한다.

1부터 target사이를 반복하며 dp[i]값을 세팅해주는 것을 목표로 한다.
사용가능한 숫자(nums)가 여러개이므로 중첩 반복이 필요하다.

현재 숫자 i에서 nums[i] 차액을 계산해본다.

i - nums[i] >= 0이면 현재 숫자 nums[i]로 딱 떨어지거나, 아니면 이전에 스텝이 더 있었을 가능성이 존재함을 뜻한다.

그럼 이 조건에 해당될 때 dp[i]값은 dp[i] + dp[i - n] 으로 세팅해주면 된다.

class Solution {
    public int combinationSum4(int[] nums, int target) {
        
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int i=1; i<=target; i++) {
            for (int n : nums) {
                if (i - n >= 0) {
                    dp[i] = dp[i] + dp[i - n];
                }
            }
        }

        return dp[target];
    }
}