【动态规划】完全背包题目应用

   点赞收藏关注
你的支持是对我最大的鼓励，我们一起积极吧!
  1.零钱兑换

标题链接： 322. 零钱兑换
标题分析：

有一堆硬币，从这些硬币中选一些硬币，看能凑成总金额amount所需的 最少的硬币个数。这是一个典范的背包题目。你可以以为每种硬币的数量是无穷的，这句话很告急。看到这个无穷你就要想到这是一个完全背包题目。
算法原理：
   1.状态表现
  dp[j] 表现：从前 i 个硬币中挑选，总和恰恰即是j，全部选法中，最少硬币个数。

   2.状态转移方程
  根据末了一个位置，分别环境
不选 i，阐明全部选法中都不包罗第 i 个硬币，相称于从去 1 ~ i - 1 这个区间去选，就是dp[i-1][j]

选1个i，这时就有 i 这个硬币了，然后仅需去 1 ~ i - 1 区间去选一个 不高出j - coins的最少硬币个数，然后在加上 i 这个硬币个数

同理，选2个 i、选3个 i都是上面的分析思绪

发现填一个状态的时间发现这个状态时间许多状态拼接而成的，这个时间我们要想到计谋把这些状态用一个大概两个状态来表现。
在完全背包那里我们已经分析过了，这里直接写，然后我们取全部环境的最小值。

   3.初始化
  

  

• 多开一行一列  
  
• 内里的值要包管后序的填表是精确的  
  
• 下标的映射关系
  

第一列不消初始化，由于用到dp[j-coins] 条件 j >= coins，以是不会越界。我们只初始化第一行。
第一行表现硬币为空，当 j = 0表现总和为0，不选就行了

当 j = 1、2、3…，硬币为空，根本凑不出总和是这些的环境。之前完全背包说过这些都给-1然后特判一下，但是在优化的时间有说过这些无效的环境仅需不让它们到场我们求dp[j]就可以了，这里我们求得是min，因此我们可以给这些位置初始化为无穷大，如许纵然环境不存在求min也不会影响。留意这里给无穷大不能给INT_MAX，起首 INT_MAX + 1 会越界Leetcode会报错，其次INT_MAX + 1 会是一个很小的数求min就会用到它。这里我们可以给0x3f3f3f3f，可以包管在这个算法中它是最大的，而且用来做加法也不会越界。

   4.填表次序
  填dp[j]会用到上面和左边的值，因此从上往下填写每一行，每一行从左往右。

   5.返回值
  dp[j] 表现：从前 i 个硬币中挑选，总和恰恰即是j，全部选法中，最少硬币个数。我们要的是从整个数组中选，总和即是amount，最少硬币个数，因此返回dp[n][amount]，但是大概整个数组也凑不出总和即是amount，以是返回判断一下
dp[n][amount] >= INF ? : -1 : dp[n][amount]

1. class Solution {
2.    
3.    
4. public:
5.     int coinChange(vector<int>& coins, int amount) {
6.    
7.    
8.         // 1.创建 dp 表
9.         // 2.初始化
10.         // 3.填表
11.         // 4.返回值
12.         const int INF = 0x3f3f3f3f;
14.         int n = coins.size();
15.         vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
16.         for(int j = 1; j <= amount; ++j) dp[0]

复制代码