力扣刷题笔记10-01背包系列

1.零钱兑换

 解题思路：

1.dp[j]代表含义：填满容量为j的背包最少需要多少硬币

2.初始化dp数组：因为硬币的数量一定不会超过amount，，因此初始化数组值为amou+1；dp[0] = 0

3.转移方程：dp[j] = min(dp[j], dp[j - coin[i]] + 1)当前填满容量j最少需要的硬币 = min( 之前填满容量j最少需要的硬币, 填满容量 j - coin[i] 需要的硬币 + 1个当前硬币）

4.返回dp[amount]，如果dp[amount]的值为amou+1没有变过，说明找不到硬币组合，返回-1.

5.注意，这道题硬币组合可重复取，所以要从前往后遍历钱的数值

代码如下：

2.零钱兑换||

 解题思路：

1.dp[j]代表含义：最多有几种方式可以凑成总钱数j；

2.初始化dp数组：dp[0] = 1，因为0元钱肯定有1种方式可以凑成

3.转移方程：dp[j] = dp[j]+dp[j - coin[i]] :

4.返回dp[amount]

5.注意，这道题硬币组合可重复取，所以要从前往后遍历钱的数值

具体代码如下：

3.一和零

 解题思路：

这道题还是0-1背包问题，具体的解题思路和第1题差不多，但是有两点不同：一是这道题是二维背包问题，一个是不能超过0的个数，一个是不能超过1的个数

                                                                                                                          二是这道题strs中字符串不可重复选取，所以遍历0和1的个数时候，要从后往前遍历

具体代码如下：

 4.最后一块石头的重量

 解题思路：

这道题的意思就是如何把数组中的所有元素分成俩部分，使这俩部分的总和的差值最小。很明显这也是0-1背包问题的变种，我们可以首先可以

求出数组元素的总和，在这里我们记为sum。然后我们遍历数组中元素，找到一种组合，该组合的总和能最大限度接近sum/2,最后的结果即为

sum-2*该组合的总和。因为这道题数组中的元素不可以重复取，所有也是从后往前遍历。

具体代码如下：

 5.数位成本和目标值最大的数字

 解题思路：这是一道完全背包问题，并且cost数组中的元素可重复取（从前往后遍历target),

①因为i遍历的顺序是从小到大，就保证了整数的高位一定大于等于整数的低位，也就保证了整数最大；

②为了保证我们dp[j]中的数位的cost相加一定等于j，而没有小于j的情况，我们特地用字符串"#"来表示无法得到的目标值(完全背包)，这样我们在进行状态转移的时候，就不会进行不合法的转移；

③而为了得到我们的目标值，进行正确的状态转移，我们又需要把dp[0]初始化为“”,因为对于任何cost的值来说，加上0都是刚好花费cost得到的目标字符串，正好是合法的情况。

具体代码如下;