【动态规划】完全背包问题应用_硬币找零 :类似完全背包问题,求组成金额 k的最少硬币数,状态转移为dp
完全背包问题应用
- 1.零钱兑换
- 2.零钱兑换 II
- 3.完全平方数
点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃
1.零钱兑换
题目链接： 322. 零钱兑换
题目分析：
有一堆硬币，从这些硬币中选一些硬币，看能凑成总金额amount所需的 最少的硬币个数。这是一个典型的背包问题。你可以认为每种硬币的数量是无限的，这句话很重要。看到这个无限你就要想到这是一个完全背包问题。
算法原理：
1.状态表示
dp[i][j] 表示：从前 i 个硬币中挑选，总和正好等于j，所有选法中，最少硬币个数。
2.状态转移方程
根据最后一个位置，划分情况
不选 i，说明所有选法中都不包含第 i 个硬币，相当于从去 1 ~ i - 1 这个区间去选，就是dp[i-1][j]
选1个i，这时就有 i 这个硬币了，然后仅需去 1 ~ i - 1 区间去选一个 不超过j - coins[i]的最少硬币个数，然后在加上 i 这个硬币个数
同理，选2个 i、选3个 i都是上面的分析思路
发现填一个状态的时候发现这个状态时候很多状态拼接而成的，这个时候我们要想到策略把这些状态用一个或者两个状态来表示。
在完全背包哪里我们已经分析过了，这里直接写，然后我们取所有情况的最小值。
3.初始化
- 多开一行一列
- 里面的值要保证后序的填表是正确的
- 下标的映射关系
第一列不用初始化，因为用到dp[i][j-coins[i]] 前提 j >= coins[i]，所以不会越界。我们只初始化第一行。
第一行表示硬币为空，当 j = 0表示总和为0，不选就行了
当 j = 1、2、3…，硬币为空，根本凑不出总和是这些的情况。之前完全背包说过这些都给-1然后特判一下，但是在优化的时候有说过这些无效的情况仅需不让它们参与我们求dp[i][j]就可以了，这里我们求得是min，因此我们可以给这些位置初始化为无穷大，这样即使情况不存在求min也不会影响。注意这里给无穷大不能给INT_MAX，首先 INT_MAX + 1 会越界Leetcode会报错，其次INT_MAX + 1 会是一个很小的数求min就会用到它。这里我们可以给0x3f3f3f3f，可以保证在这个算法中它是最大的，并且用来做加法也不会越界。
4.填表顺序
填dp[i][j]会用到上面和左边的值，因此从上往下填写每一行，每一行从左往右。
5.返回值
dp[i][j] 表示：从前 i 个硬币中挑选，总和正好等于j，所有选法中，最少硬币个数。我们要的是从整个数组中选，总和等于amount，最少硬币个数，因此返回dp[n][amount]，但是可能整个数组也凑不出总和等于amount，所以返回判断一下
dp[n][amount] >= INF ? : -1 : dp[n][amount]
class Solution { public: int coinChange(vector<int>& coins, int amount) { // 1.创建 dp 表 // 2.初始化 // 3.填表 // 4.返回值 const int INF = 0x3f3f3f3f; int n = coins.size(); vector<vector<int>> dp(n + 1, vector<int>(amount + 1)); for(int j = 1; j <= amount; ++j) dp[0]
