[DP] 377. Combination Sum IV

377. Combination Sum 4 

target 을 만들기 위한 숫자 조합 세기. 

target에서 1~3중에 숫자를 하나 골라서 뺏을때,  앞서 만들었던 DP를 통해서, 그 수를 만들수 있는 경우의 갯수를 더해주면 된다. 

DP를 저장 할 공간은 1D면 된다. 왜나면, 1을 만드는 경우의 개수, 2를 만드는 경우의 개수... 식으로 1차원만 있으면 된다. 

target =4 

target - 고른값 

target -1 = 3 -> dp[3] 

target -2 = 2 -> dp[2]

target -3 = 1 -> dp[1] 

 

target 4를 만들 수 있는 경우의 수는 dp[3] + dp[2] + dp[1]

 

 

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target+1, 0);
        dp[0] = 1;
        
        for(int i=1; i <= target; i++){            
            for(int j=0;j<nums.size();j++){
                if(i - nums[j] >= 0)
                    dp[i] += dp[i-nums[j]];                    
            }
        }
        
        return dp[target];
    }
};