BackPack 4

Solution

[1, 2, 5, 6] S = 10

无限多的硬币，构成背包为10的方案数。

dp[i][j] = dp[i-1][j] + dp[i][j-A[i]]

可以填到11

Code

/**

 * @param nums an integer array and all positive numbers, no duplicates
 * @param target an integer
 * @return an integer
 */
int backPackIV(vector<int>& nums, int target) {
    // Write your code here
    int n = nums.size();
    if(n == 0)
    {
        return 0;
    }

    vector<vector<int>> dp;
    for(int i = 0; i < n+1; i++)
    {
        vector<int> tmp(target+1, 0);
        tmp[0] = 1;
        dp.push_back(tmp);
    }

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

    return dp[n][target];
}