蓝桥杯第六讲--简单dp【例题】-Toy模板网

这篇具有很好参考价值的文章主要介绍了蓝桥杯第六讲--简单dp【例题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第六讲：简单dp【例题】

本篇博客所包含习题有：
👊01背包问题
👊摘花生
👊最长上升子序列

简单dp【习题】见博客：蓝桥杯第六讲–简单dp【习题】

博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！

01背包问题

题目要求

题目描述：

有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。

第 $i$ 件物品的体积是 $v_i$ ，价值是 $w_i$ 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式：

第一行两个整数， $N ， V$ ，用空格隔开，分别表示物品数量和背包容积。

接下来有 $N$ 行，每行两个整数 $v_i,w_i$ ，用空格隔开，分别表示第 $i$ 件物品的体积和价值。

输出格式：

输出一个整数，表示最大价值。

数据范围：

$0 < N, V \leq 1000$
$0<v_i,w_i≤1000$

输入样例：

4 5
1 2
2 4
3 4
4 5

输出样例：

8

思路分析

朴素版

蓝桥杯第六讲--简单dp【例题】
上图其实已经说的很详细了，用文字去解释就是我们定义的状态： $f [i] [j]$ ，就是表示从前 $i$ 个物品里面进行选择，选择的总体积不超过 $j$ 的最大值，我们的状态转移方程推导：对于第 $i$ 个商品，我们有两种决策：选它或者不选它，如果不选择它，对应此时的状态就是 $f [i - 1] [j]$ ，如果选择它，对应此时的状态就是 $f [i - 1] [j - v [i]] + w [i]$ ，每次决策都取两者的最大值。

优化

通过朴素版的分析，可以明白：对于第一位状态，我们其实只会用到它的上一维状态去进行优化，如我们在计算 $f [i] [j]$ 的时候，只会用到 $f [i - 1]$ ，对于 $f [i - 2]$ 这种状态我们是不会使用的，所以我们可以把第一维给去掉，那么代码1：

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

就会变成代码2：

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

我们观察到：f[j] = f[j];是一个恒等式，故可以删掉，变成代码3：

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

我们来对比一下代码1和代码3，发现它们两个其实是由本质的区别的，我们在代码1中的装填转移方程中所用到的f[i - 1][j - v[i]] + w[i]是第 $i - 1$ 层的变量，但是在代码3中，由于我们的 $j$ 是从小到大进行枚举的，且 $j - v [i]$ 肯定是小于 $j$ 的，所以我们在计算 $f [j]$ 的时候（第 $i$ 层），此时我们的 $f [j - v [i]]$ 已经被计算过（第 $i$ 层），故代码3中的f[j - v[i]] + w[i]其实是属于第 $i$ 层的，这样显然是错误的，我们可以采用一种取巧的方法：第二层 $f o r$ 循环从大到小进行更新，这时，第 $i$ 层的 $f [j]$ 在计算的时候，由于 $j - v [i]$ 肯定小于 $j$ ，即此时的 $f [j - v [i]]$ 其实还是第 $i - 1$ 层，这样就和代码1是保持一致的了。

代码（朴素版）

#include <iostream>
#include <cstring>
#include <algorithm>

const int N = 1010;

int v[N], w[N];
int f[N][N];

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
        cin >> v[i] >> w[i];

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

    cout << f[n][m] << endl;

    return 0;
}

代码（优化）

#include <iostream>
#include <cstring>
#include <algorithm>

const int N = 1010;

int v[N], w[N];
int f[N];

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) 
        cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- ) 
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

摘花生

题目要求

题目描述：

Hello Kitty 想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty 只能向东或向南走，不能向西或向北走。

问 Hello Kitty 最多能够摘到多少颗花生。
蓝桥杯第六讲--简单dp【例题】

输入格式：

第一行是一个整数 $T$ ，代表一共有多少组数据。

接下来是 $T$ 组数据。

每组数据的第一行是两个整数，分别代表花生苗的行数 $R$ 和列数 $C$ 。

每组数据的接下来 $R$ 行数据，从北向南依次描述每行花生苗的情况。每行数据有 $C$ 个整数，按从西向东的顺序描述了该行每株花生苗上的花生数目 $M$ 。

输出格式：

对每组输入数据，输出一行，内容为 Hello Kitty 能摘到得最多的花生颗数。

数据范围：

$1 \leq T \leq 100,$
$1 \leq R, C \leq 100,$
$0 \leq M \leq 1000$

输入样例：

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

输出样例：

8
16

思路分析

拿到一个题目后，我们分为两步去考虑这个问题：
第一步：把题目进行抽象：其实就是对于一个矩形，我们从它的左上角走到右下角，每一个点上都一个数值，走到一个点后就加上这个点的值，每次只能往右走或者往下走，问走到右下角的话，数值的累计最大值是多少。
第二步：进行 $d p$ 分析：比如我们现在在 $[i, j]$ 这个点上， $d p$ 的关键就是分析这个点可以由哪个点转换而来：显然，对于这个点而言，根据题意可以由上面的一个点转换，亦可由左边的一个点转换过来，而我们的需求为最大值，故我们可以得到状态转移方程：f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int w[N][N];
int f[N][N];

int main()
{
    int t;
    cin >> t;
    
    while (t -- ) 
    {
        int r, c;
        cin >> r >> c;
        for (int i = 1; i <= r; i ++ ) 
            for (int j = 1; j <= c; j ++ ) 
                cin >> w[i][j];
                
        for (int i = 1; i <= r; i ++ ) 
            for (int j = 1; j <= c; j ++ )
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];
                
        cout << f[r][c] << endl;
    }
    
    return 0;
}

最长上升子序列

题目要求

题目描述：

给定一个长度为 $N$ 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式：

第一行包含整数 $N$ 。

第二行包含 $N$ 个整数，表示完整序列。

输出格式：

输出一个整数，表示最大长度。

数据范围：

$1 \leq N \leq 1000 ，$
$10^9≤$ 数列中的数 $10^9$

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

思路分析

蓝桥杯第六讲--简单dp【例题】
我们要求的是最长上升子序列，状态表示 $f [i]$ 表示的是在以第 $i$ 个数为结尾的最长上升子序列的长度，所以我们的状态转移就是去枚举 $j$ ， $j$ 的范围是 $[1, i - 1]$ ，如果有 $a [j] < a [i]$ ，那么我们就取一个最大值：f[i] = max(f[i], f[j] + 1);，注意，由于我们的状态定义，故 $f [i]$ 的最小值是 $1$ （它自己单独为一个最长上升子序列），最后的结果需要重新遍历一遍，取得所有 $f [i]$ 的最大值。文章来源地址https://www.toymoban.com/news/detail-424501.html

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int a[N];
int f[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        cin >> a[i];
        
    for (int i = 1; i <= n; i ++ )
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++ ) 
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
    }
    
    int res = 0;
    for (int i = 1; i <= n; i ++ ) 
        res = max(res, f[i]);
    
    cout << res << endl;
    
    return 0;
}