【十八】【动态规划】1049. 最后一块石头的重量 II、【模板】完全背包_牛客题霸_牛客网、322. 零钱兑换，三道题目深度解析

发布时间：2024年01月08日

动态规划

动态规划就像是解决问题的一种策略，它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题，并将每个小问题的解保存起来。这样，当我们需要解决原始问题的时候，我们就可以直接利用已经计算好的小问题的解，而不需要重复计算。

动态规划与数学归纳法思想上十分相似。

数学归纳法：

基础步骤（base case）：首先证明命题在最小的基础情况下成立。通常这是一个较简单的情况，可以直接验证命题是否成立。
归纳步骤（inductive step）：假设命题在某个情况下成立，然后证明在下一个情况下也成立。这个证明可以通过推理推断出结论或使用一些已知的规律来得到。

通过反复迭代归纳步骤，我们可以推导出命题在所有情况下成立的结论。

动态规划：

状态表示：
状态转移方程：
初始化：
填表顺序：
返回值：

数学归纳法的基础步骤相当于动态规划中初始化步骤。

数学归纳法的归纳步骤相当于动态规划中推导状态转移方程。

动态规划的思想和数学归纳法思想类似。

在动态规划中，首先得到状态在最小的基础情况下的值，然后通过状态转移方程，得到下一个状态的值，反复迭代，最终得到我们期望的状态下的值。

接下来我们通过三道例题，深入理解动态规划思想，以及实现动态规划的具体步骤。

1049. 最后一块石头的重量 II - 力扣（LeetCode）

题目解析

因此我们直接把问题转化为在一堆石头中，挑选一些数，使得这些数前面的符号为正数，剩下没有挑选的数，前面的负号为负数。

假设原始石头总重量为sum，某一种选法，挑选出的石头重量和为sum1，剩下没有被挑选到的石头重量和为sum2。我们可以得到sum=sum1+sum2，sum1-sum2=最后一块石头的重量。

而我们需要使sum1-sum2尽可能小，等价于sum1和sum2尽可能相等。那么这是怎么得出来的呢？

现在的问题转变为使得sum1尽可能等于sum2。

而sum2=sum-sum1，所以等价于sum1尽可能等于sum/2。

现在的问题转化为，在一堆数中挑选一些数，使得这些数和尽可能等于一个定值。

而背包问题解决的问题就是组合问题，在一些物品中挑选一些物品。很容易可以想到使用动态规划的方法去解决这个问题。

状态表示

01背包问题是一个模版，我们根据这个模版可以定义出状态表示。

01背包问题的状态表示是，

定义dp[i][j]表示从前i个物品中挑选，总体积不超过j，所有选法中，所能达到的最大价值。

定义dp[i][j]表示从前i个物品中挑选，总体积恰好为j，所有选法中，所能达到的最大价值。

因此我们可以定义dp[i][j]表示从前i个石头中挑选，总重量不超过j，所有选法中，所能达到的最大重量。

状态转移方程

状态转移方程的推导，通常都是根据最后一个位置元素的状况进行分类讨论。

如果挑选第i个石头，
1. 如果j-stones[i]<0, 此时表示第i个石头重量超过j，而要求是重量不超过j，所以此时dp[i][j]=0。
2. 如果j-stones[i]=0, 此时表示第i个石头重量等于j，选完第i个石头之后就不能再选了，此时dp[i][j]=stones[i]。
3. 如果j-stones[i]>0, 此时选择了第i个石头，剩下还可以使用的重量是j-stones[i]此时dp[i][j]=dp[i-1][j-stones[i]]+stones[i]。
如果不挑选第i个石头，此时dp[i][j]=dp[i-1][j]。

如果j-stones[i]==0，此时dp[i-1][0]也等于0，dp[i-1][j-stones[i]]+stones[i]=stones[i]。

所以这种情况可以与j-stones[i]>0的情况进行合并。

综上所述，将上述情况进行合并和简化，得到状态转移方程，

dp[i][j] = dp[i - 1][j]; if (j >= stones[i - 1]) dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);

因为dp[i][j]表示从前i个石头中挑选，总重量不超过j，所有选法中，所能达到的最大重量。

所以实际上dp表多添加了一行。下标1-n就是我们需要填写的状态对应下标。

所以下标映射到stones需要减1。

初始化

根据状态转移方程，我们知道在推导（i，j）位置的状态时，需要用到（i-1，j）（i-1，j-stones[i-1]）位置的状态，以及stones[i-1]的数据。

而使用（i-1，j-stones[i-1]）的时候，if (j >= stones[i - 1])，j-stones[i-1]一定不会越界，所以只需要判断（i-1，j）和stones[i-1]的情况。

在推导蓝色部分的状态时，会发生越界的情况，此时没有前驱，所以需要对蓝色部分位置进行初始化。

此时i=0，表示不选石头，达到的最大价值为0。故第一行全部初始化为0。

填表顺序

根据状态转移方程，我们知道在推导（i，j）位置的状态时，需要用到（i-1，j）（i-1，j-stones[i-1]）位置的状态。

固定i，改变j， i的变化需要从小到大，j的变化可以从小到大也可以从大到小。
固定j，改变i， j-stones[i-1]一定小于j，所以j的变化需要从小到大，因为需要用到（i-1，j）位置的状态，所以i的变化需要从小到大。

返回值

dp[i][j]表示从前i个石头中挑选，总重量不超过j，所有选法中，所能达到的最大重量。

根据题目意思，我们需要统计总石头重量sum，然后返回sum-2*dp[n][m] （n，m分别是石头的个数，sum/2）

代码实现

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for (auto x : stones)
            sum += x;
        int n = stones.size(), m = sum / 2;
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= stones[i - 1])
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
            }
        // 3. 返回结果
        return sum - 2 * dp[n][m];
    }
};

【模板】完全背包_牛客题霸_牛客网

题目解析

第一问

状态表示

因为完全背包本质上和01背包是一样的，在一些物品中挑选出一些物品，同样是组合的问题。所以状态表示是一样的，这两个问题的区别就是物品个数，完全背包物品有无限个，01背包物品是有限个。

因此我们用01背包的状态表示就可以了，即定义dp[i][j]表示从前i个物品中挑选，总体积不超过j，所有选法中，所能达到的最大价值。

状态转移方程

状态转移方程的推导，通常都是根据最后一个位置元素的状况进行分类讨论。

如果选0个第i个物品，此时dp[i][j]=dp[i-1][j]。
如果选1个第i个物品，此时dp[i][j]=dp[i-1][j-v[i]]+w[i]。
如果选2个第i个物品，此时dp[i][j]=dp[i-1][j-2*v[i]]+2*w[i]。 ............
如果选择n个第i个物品，此时dp[i][j]=dp[i-1][j-n*v[i]]+n*w[i]。一直到背包装不下了为止。

综上所述dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i],......)

对于上述的情况，我们发现了一些很有趣的东西，dp[i-1][j],dp[i-1][j-v[i]]+w[i]...每一次横坐标不变，纵坐标减少v[i]，然后整体加上w[i]。

根据这个规律我们可以尝试推导dp[i-1][j-v[i]]，得到dp[i][j-v[i]]=max(dp[i-1][j-v[i]],dp[i-1][j-2*v[i]]+w[i],......),为了统一表示，推导dp[i][j-v[i]]+w[i]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j-2*v[i]]+2*w[i],......)

此时我们发现dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i],......)和dp[i][j-v[i]]+w[i]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j-2*v[i]]+2*w[i],......)后面部分是相同的。

因此我们可以写成这样，dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i])；

综上所述状态转移方程为，

    dp[i][j] = dp[i - 1][j];
    if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);

初始化

根据状态转移方程，我们在推导（i，j）位置的时候需要用到（i-1，j）（i，j-v [i]）位置的状态。但是只有j>=v[i]的时候才会使用(i,j-v[i])的状态，所以j-v[i]一定不会越界，我们只需要考虑（i-1，j）的状态就可以了。

所以在推导第一行的状态时，会发生越界的情况，此时没有前驱状态值。所以我们需要初始化这些位置的状态。

初始化第一行，此时i==0，表示不选物品，此时dp[i][j]=0；

因此我们不需要进行初始化操作。

填表顺序

根据状态转移方程，我们在推导（i，j）位置的时候需要用到（i-1，j）（i，j-v [i]）位置的状态。

    dp[i][j] = dp[i - 1][j];
    if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);

固定i改变j， i的变化需要从小到大，由于需要用到（i，j-v[i]）的状态，所以j的变化也需要从小到大。
固定j改变i， j-v[i]一定比j小，所以j的变化需要从小到大，由于需要用到（i-1，j）的状态，所以i的变化需要从小到大。

返回值

根据状态表示，定义dp[i][j]表示从前i个物品中挑选，总体积不超过j，所有选法中，所能达到的最大价值。结合题目意思，我们需要打印dp[n][V] (n,V分别表示物品数，和背包体积)

第二问

状态表示

第二问需要求恰好体积为V时，背包所能达到的最大价值。

在第一问的基础上，我们很容易定义这样一个状态表示，定义dp[i][j]表示从前i个物品中挑选，总体积恰好为j，所有选法中所能达到的最大价值。

状态转移方程

dp[i][j]=-1表示不存在。

如果选0个第i个物品，此时dp[i][j]=if(dp[i-1][j]！=-1) dp[i-1][j]。
如果选1个第i个物品，此时dp[i][j]=if(dp[i-1][j]！=-1) dp[i-1][j-v[i]]+w[i]。
如果选2个第i个物品，此时dp[i][j]=if(dp[i-1][j]！=-1) dp[i-1][j-2*v[i]]+2*w[i]。 ............
如果选择n个第i个物品，此时dp[i][j]=if(dp[i-1][j]！=-1) dp[i-1][j-n*v[i]]+n*w[i]。一直到背包装不下了为止。

综上所述dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i],......) （每种情况存在才考虑）

对于上述的情况，我们发现了一些很有趣的东西，dp[i-1][j],dp[i-1][j-v[i]]+w[i]...每一次横坐标不变，纵坐标减少v[i]，然后整体加上w[i]。

此时我们发现dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i],......)和dp[i][j-v[i]]+w[i]=max(dp[i-1][j-v[i]]+w[i],dp[i-1][j-2*v[i]]+2*w[i],......)后面部分是相同的。

因此我们可以写成这样，dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i])；（每种情况存在才考虑）

综上所述状态转移方程为，

    dp[i][j] = dp[i - 1][j];
    if (j >= v[i] && dp[i][j - v[i]] != -1)
        dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
}

使用dp[i][j-v[i]]+w[i]的时候需要判断dp[i][j-v[i]]是否存在，如果不存在dp[i][j-v[i]]=-1,但是加上w[i]之后，可能会取到，所以需要判断一下是否存在，如果不想判断可以把不存在的情况，价值改为-0x3f3f3f3f，这样就不会取到了。

初始化

所以在推导第一行的状态时，会发生越界的情况，此时没有前驱状态值。所以我们需要初始化这些位置的状态。

初始化第一行，此时i==0，表示不选物品，此时dp[i][j]=0；

因此我们不需要进行初始化操作。

填表顺序

根据状态转移方程，我们在推导（i，j）位置的时候需要用到（i-1，j）（i，j-v [i]）位置的状态。

    dp[i][j] = dp[i - 1][j];
    if (j >= v[i] && dp[i][j - v[i]] != -1)
        dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
}

固定i改变j， i的变化需要从小到大，由于需要用到（i，j-v[i]）的状态，所以j的变化也需要从小到大。
固定j改变i， j-v[i]一定比j小，所以j的变化需要从小到大，由于需要用到（i-1，j）的状态，所以i的变化需要从小到大。

返回值

根据状态表示定义dp[i][j]表示从前i个物品中挑选，总体积恰好为j，所有选法中所能达到的最大价值。结合题目意思，我们需要打印dp[n][V] (n,V分别表示物品数，和背包体积)，并且打印前还需要判断dp[n][V]是否存在， cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;存在打印dp[n][V]不存在打印0。

代码实现

#include<iostream>
#include<string.h>
using namespace std;

const int N = 1010;

int n, V, v[N], w[N];
int dp[N][N];

int main() {

    cin >> n >> V;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= V; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }

    cout << dp[n][V] << endl;
 //第二问
    memset(dp, 0, sizeof dp);
    for (int j = 1; j <= V; j++) dp[0][j] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= V; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i] && dp[i][j - v[i]] != -1)
                dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
        }

    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;
    return 0;
}

322. 零钱兑换 - 力扣（LeetCode）

题目解析

状态表示

完全背包同样是一个模版，我们根据完全背包的状态表示，来定义我们需要的状态表示。

完全背包的状态表示是，

定义dp[i][j]表示从前i个物品中挑选，总体积不超过j，所有选法中，所能达到的最大价值。

定义dp[i][j]表示从前i个物品中挑选，总体积恰好为j，所有选法中，所能达到的最大价值。

结合题目意思，我们可以定义dp[i][j]表示从前i个硬币中挑选，总硬币面额恰好为j，所有选法中，所需硬币个数的最小值。

状态转移方程

选取0个第i个硬币，此时dp[i][j]=dp[i-1][j]。(如果存在）
选取1个第i个硬币，此时dp[i][j]=dp[i-1][j-coins[i]]+1。(如果存在）
选取2个第i个硬币，此时dp[i][j]=dp[i-1][j-2*coins[i]]+2。(如果存在） ............
选取n个第i个物品，此时dp[i][j]=dp[i-1][j-n*coins[i]]+n。(如果存在）一直到背包装不下了为止。

综上所述dp[i][j]=min(dp[i-1][j],dp[i-1][j-coins[i]]+1,......)

对于上述的情况，我们发现了一些很有趣的东西，dp[i-1][j],dp[i-1][j-coins[i]]+1...每一次横坐标不变，纵坐标减少coins[i]，然后整体加上1。

根据这个规律我们可以尝试推导dp[i-1][j-coins[i]]，得到dp[i][j-coins[i]]=min(dp[i-1][j-coins[i]],dp[i-1][j-2*coins[i]]+1,......),为了统一表示，推导dp[i][j-coins[i]]+1=min(dp[i-1][j-coins[i]]+1,dp[i-1][j-2*coins[i]]+2,......)

此时我们发现dp[i][j]=min(dp[i-1][j],dp[i-1][j-coins[i]]+1,......)和dp[i][j-coins[i]]+1]=min(dp[i-1][j-coins[i]]+1,dp[i-1][j-2*coins[i]]+2,......)后面部分是相同的。

因此我们可以写成这样，dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i]]+1)；

我们可以设置，不存在的情况，dp值为0x3f3f3f3f，此时就不会选到不存在的情况。

综上所述，状态转移方程为，

    dp[i][j] = dp[i - 1][j];
    if (j >= coins[i - 1])
        dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);

为什么这里不用判断是否存在，因为即使不存在，也不会选到dp[i][j - coins[i - 1]] + 1，不存在时，dp中存的值足够大，加上1也不会选到。

初始化

根据状态转移方程，我们在推导（i，j）位置的时候需要用到（i-1，j）（i，j-coins [i]）位置的状态。但是只有j>=coins[i]的时候才会使用(i,j-coins[i])的状态，所以j-coins[i]一定不会越界，我们只需要考虑（i-1，j）的状态就可以了。

所以在推导第一行的状态时，会发生越界的情况，此时没有前驱状态值。所以我们需要初始化这些位置的状态。

初始化第一行，此时i==0，表示不选硬币，此时dp[i][j]=0；

因此我们不需要进行初始化操作。

填表顺序

根据状态转移方程，我们在推导（i，j）位置的时候需要用到（i-1，j）（i，j-coins [i]）位置的状态。

    dp[i][j] = dp[i - 1][j];
    if (j >= coins[i - 1])
        dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);

固定i改变j， i的变化需要从小到大，由于需要用到（i，j-coins[i]）的状态，所以j的变化也需要从小到大。
固定j改变i， j-coins[i]一定比j小，所以j的变化需要从小到大，由于需要用到（i-1，j）的状态，所以i的变化需要从小到大。

返回值

根据状态表示定义dp[i][j]表示从前i个硬币中挑选，总硬币面额恰好为j，所有选法中，所需硬币个数的最小值。结合题目意思，我们需要打印dp[n][amount] (n,V分别表示物品数，和目标值)。并且需要判断是否存在，dp[n][amount] >= INF ? -1 : dp[n][amount];如果不存在返回-1，存在就返回dp[n][amount]。

代码实现


class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        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][j] = INF;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j <= amount; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i - 1])
                    dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
            }
        return dp[n][amount] >= INF ? -1 : dp[n][amount];
    }
};

结尾

今天我们学习了动态规划的思想，动态规划思想和数学归纳法思想有一些类似，动态规划在模拟数学归纳法的过程，已知一个最简单的基础解，通过得到前项与后项的推导关系，由这个最简单的基础解，我们可以一步一步推导出我们希望得到的那个解，把我们得到的解依次存放在dp数组中，dp数组中对应的状态，就像是数列里面的每一项。最后感谢您阅读我的文章，对于动态规划系列，我会一直更新，如果您觉得内容有帮助，可以点赞加关注，以快速阅读最新文章。

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。

谢谢您的支持，期待与您在下一篇文章中再次相遇！

文章来源:https://blog.csdn.net/m0_74163972/article/details/135460266
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！