LC518
零钱兑换 II
背包 DP · 组合数可视化:动态规划表coins=[1,2,5],amount=5 组合方式数 4。
时间 O(coins·amount)空间 O(amount)
题目1 / 18
题目与输入建立输入、目标与算法心智
金额轴从 0 到目标 amount；dp[0]=1 表示“什么都不选”这一种空组合。
正在加载组合工厂...
当前发生了什么
coins=[1,2,5],amount=5 组合方式数 4。
机器状态
dp 计数数组。
为什么正确
完全背包计数 dp[j]+=dp[j-coin]。
不变量
顺序无关,硬币外层循环。
面试怎么说
完全背包计数 O(coins·amount)。
人类输入
coins=[1,2,5],amount=5 组合方式数 4。
机制
完全背包计数 dp[j]+=dp[j-coin]。
机器状态
dp 计数数组。
可观察结果
4 种组合。
不变量
- · 顺序无关,硬币外层循环。
常见误区
- · 与排列不同,内外循环顺序固定。
迁移练习
- · LC322 最少硬币
- · LC377 组合总和 IV
面试怎么答
完全背包计数 O(coins·amount)。