377. Combination Sum IV

做题历程：

1. 2016/Sep/01, 未独立解出

其实本题并不难的，估计是太久没有高强度做题，导致手生了，今后的套路是每天刷1道题，直到今年年底。之后的路再说，反正先把2016年过了，之后再考虑跳到大公司。。

言归正传，本题我最开始用的是recursive dfs的方法，可惜超时了，这个可以想象出来，毕竟有大量的重复。后来看了下答案，有一个用dynamic programming的方法不错，虽然不是最好的，但是应该可以算是最好理解的，基本套路是设定一个vector<int> dp(target + 1)。dp[i]就是和为i的所有可能，他可以通过一个for(int j = 0; j < nums.size(); ++j)得出，只要nums[j]比i小，就可以累加： dp[i] += dp[i - nums[j]]。 完整代码如下：

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