解释一下上面的动态规划转移方程
时间: 2023-08-14 11:07:28 浏览: 77
动态规划之状态转移方程
动态规划转移方程 dp[i] = dp[i] + dp[i-coin] 的含义是,对于金额 i,我们可以用当前遍历到的硬币面额 coin 来组成,那么组成金额 i 的不同组合数等于两部分之和:
1. 不使用当前硬币 coin,那么组成金额 i 的组合数为 dp[i]。
2. 使用当前硬币 coin,那么组成金额 i 的组合数为 dp[i-coin]。
因此,我们将这两部分的组合数相加,就得到了组成金额 i 的不同组合数。这个转移方程的含义是在计算动态规划数组时,我们要考虑所有可能的硬币组合方式。
通过遍历硬币面额和金额,我们可以依次更新dp数组的值,最终得到dp[amount]的结果,即用给定的硬币面额组成指定金额的不同组合数。
阅读全文