题解 | #兑换零钱(二)#

设dp[j]表示凑成j元一共有多少方法，dp[0] = 1，凑成0元只有一种方法，就是啥也不拿出来
转移方程：dp[j] = dp[j] + dp[j-nums[i]]
这里的dp表是由二维的dp表压缩成一维的，还有一层用第i个硬币的含义。假设计算用第i个硬币凑成j元时候，等号左边是等待更新的状态，而等号右边依旧表示的i-1硬币时候的状态。
转移方程表示用第i个硬币凑成j元的时候，有两种方式，要么直接i-1个硬币的时候就凑成了  要么i-1个时候凑成j-num[i],剩下的第i个硬币凑齐.注意状态的依赖关系,选择填充方式

int change(int target, int* nums, int numsLen ) 
{
    // write code here
    int dp[target+1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1;
    
    for( int i = 0; i < numsLen; ++i )
    {
        for( int j = nums[i]; j <= target; ++j )
        {
            dp[j] = dp[j] + dp[j - nums[i]];
        }
    }
    return dp[target];
}