题解 | #兑换零钱(二)#
兑换零钱(二)
https://www.nowcoder.com/practice/521cead04d1442899767578c3aa395f0
设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];
}
查看15道真题和解析
