dp算法入门（闫氏dp分析法）

dp算法

• 什么是dp
• 一、核心思想
• 二、dp入门
  • 1.线性dp
  • 2 .未完待续
• 总结

---

什么是dp

dp即是动态规划，是一种把问题分成若干个有关联的子问题来求解复杂问题的方法。dp常常适用于有重叠的子问题和最有子结构性质的问题(★ dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.)简单来说，dp就是将复杂问题分成小问题然后表示每种问题的‘状态’并加以计算。

一、核心思想

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

二、dp入门

1.线性dp

T1:acwing898（模板）

题目描述:给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

1. 7
2. 3 8
3. 8 1 0
4. 2 7 4 4
5. 4 5 2 6 5

输入格式

第一行包含整数 n，表示数字三角形的层数。

接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

对于此题，先来研究一般性，假设我们从最后一行开始（最后一行每一个数都可能成为起点），依次往上走，知道走到第一个点（不妨将图记作g[][],第一个点记作g[1][1],为什么不从0开始作为下标，后面会分析）假设一直往上走，走到了g[i][j]这个点，那么对于g[i][j]，来看它来源

            g[i][j]

        g[i+1][j]  g[i+1][j+1]

由题意，可以知道点g[i][j]，只能由g[i+1][j],g[i+1][j+1]两个点直接得到，我们不妨定义数组f[][]，让f[i][j]表示为所有从最后一行走到点i，j的距离的最大值。这个f数组就是这题的状态表示,那么怎么计算f[i][j]呢，我们已经推出了点（i，j）只能由（i + 1，j）和（i + 1，j + 1）两个点到，所以怎么求     f[i][j]就转化为了只需要求f[i + 1][j] 和 f[i + 1][j + 1]的最大值，再加上i，j上的值，即g[i][j]即可，公式表达如下：

我们可以对代码进行空间的优化，省略初始化的步骤，让g数组直接表示为dp数组也是可行的：

1. #include
2. #include
3. #include
6. using namespace std;
7. const int N = 510;
8. int g[N][N], n;//g数组存图，f数组表示所有以（i，j）为终点的方案的数字和最大值
11. int main()
12. {
13. scanf("%d", &n);
15. for(int i = 1; i <= n; i++)//下标从1开始，因为我们后续可能会用到 i - 1， 防止数组越界
16. for(int j = 1; j <= i; j++) scanf("%d", &g[i][j]);
18. //dp:从倒数第二行开始往上走，终点是（1，1）
19. for(int i = n - 1; i >= 1; i--)
20. for(int j = 1; j <= i; j++) g[i][j] = max(g[i + 1][j], g[i + 1][j + 1]) + g[i][j];
22. printf("%d",g[1][1]);
24. return 0;
25. }

应用：

T2:acwing1015

题目描述：

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

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

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

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

问Hello Kitty最多能够摘到多少颗花生。

起
				终

输入格式：

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

接下来是T组数据。

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

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

状态表示:同样于上题，我们用g数组存每个格子上的花生数，f数组存所有以那个点为终点的花生数的最大值，对于点(i, j)，它只能由上面或者左边的点得到，所以(i, j)上的最大值应该是(i - 1, j) 和(i, j - 1) 两个点的最大值再加上(i, j) 上的花生数

状态计算：

优化：

1. //空间优化
2. #include
3. #include
4. #include
7. using namespace std;
8. const int N = 110;
9. int t, n, m, g[N][N];
12. int main()
13. {
14. scanf("%d", &t);
16. while(t -- )
17. {
18. scanf("%d%d", &n, &m);
20. for(int i = 1; i <= n; i++)
21. for(int j = 1; j <= m; j++) scanf("%d", &g[i][j]);
23. for(int i = 1; i <= n; i++)
24. for(int j = 1; j <= m; j++) g[i][j] = max(g[i - 1][j], g[i][j - 1]) + g[i][j];
26. printf("%d\n", g[n][m]);
27. }
29. return 0;
30. }

T3:acwing1018

题目描述：

一个商人穿过一个 N×N 的正方形的网格，去参加一个非常重要的商务活动。

他要从网格的左上角进，右下角出。

每穿越中间 11 个小方格，都要花费 11 个单位时间。

商人必须在 (2N−1)个单位时间穿越出去。

而在经过中间的每个小方格时，都需要缴纳一定的费用。

这个商人期望在规定时间内用最少费用穿越出去。

请问至少需要多少费用？

注意：不能对角穿越各个小方格（即，只能向上下左右四个方向移动且不能离开网格）。

输入格式：

第一行是一个整数，表示正方形的宽度 N。

后面 N 行，每行 N 个不大于 100100 的正整数，为网格上每个小方格的费用。

状态表示：仍然用g数组存图，f数组表示为 f[i][j]是所有以(i,j)为终点的方案中费用最小的值，相较于上一题，这题多了一个限制条件，就是遍历的格子数要 <= 2n - 1。

状态分析：先说结论，这题可以套用上一题的模板，也就是说可以不需要考虑时间的限制条件，为什么呢？

如上图，我们假设上图的行列数都为n，那么如果只允许每次只能向下或者向右的情况下，从起点(1,1)走到终点(n,n)所需要的时间为：n - 1 + n == 2 * n - 1(行需要n - 1的时间而列需要n的时间)

好的，现在我们假设商人在走的过程中至少向上或者向左走了一步，首先，我们不妨定义正位移为向下或者向右的运动，负位移为向上或者向左的运动，为什么呢？因为只有向下和向右才能到达终点，而向左和向上不行。好回归正题，假设从(i, j)向上或向左走了一次，那么回到这个点就需要额外的一次，也就说我们额外多走了一次才到(i, j)，所以从(1,1) 到 (i, j) 再到 (n, n) 所需要的最短时间就是2n - 1 +1 > 2n - 1

所以我们得出结论：如果时间限制为2n - 1，商人只能向下向右，不能向上向左走

代码实现：

1. #include
2. #include
3. #include
6. using namespace std;
7. const int N = 110;
8. int g[N][N], f[N][N], n;
11. int main()
12. {
13. scanf("%d", &n);
15. for(int i = 1; i <= n; i++)
16. for(int j = 1; j <= n; j++) scanf("%d", &g[i][j]);
18. memset(f, 0x3f, sizeof f);//要求最小值，所以初始化f一个较大的值，每次更新
19. f[1][1] = g[1][1];//起点
21. for(int i = 1; i <= n; i++)
22. for(int j = 1; j <= n; j++)
23. {
24. //每一次用上和左两个点来更新当前点
25. f[i][j] = min(f[i][j], f[i - 1][j] + g[i][j]);
26. f[i][j] = min(f[i][j], f[i][j - 1] + g[i][j]);
27. }
29. printf("%d", f[n][n]);
31. return 0;
32. }

求最小值时没法优化空间，因为min(g[i - 1][j] + g[i][j], g[i][j]) 只会等于g[i][j]，换言之g数组不能被当作f数组进行更新。

T4:acwing1027

题目描述：

设有 N×N 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：

某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。

在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。

输入格式

第一行为一个整数N，表示 N×N 的方格图。

接下来的每行有三个整数，第一个为行号数，第二个为列号数，第三个为在该行、该列上所放的数。

行和列编号从 11 开始。

一行“0 0 0”表示结束。

状态表示：存图同样是用g数组来图， 但是该怎么表示状态呢，传统的两维表示(f[][])已经不能很好

的适用了，因为这道题人走了两次，而第一次走的过程中会将经历的每个点的值变为0，所以不应

该将过程分开成两次独立的事件来看。不妨视作人从起点到终点同时开走两次，并且仍然保持每次

所走到的点的值变为0，那么理论上我们应该用4个状态来表示状态，不妨分别记作f(i1，j1，i2，

j2)就是两次运动的横纵坐标，但是如果数据量稍微大一点的话比如1e2级别，f数组可能就会爆内

存。所以要对f数组优化，优化的方式可以为f(k,i1,i2),其中k表示为每一次运动的横纵坐标之和，由

于我们的f数组表示人从起点到终点同时的运动两次，所以两次的横纵坐标之和一定会相等。

状态分析：对于该运动，设两次分运动的点的横坐标分别为i1， i2， 横纵坐标为k，则横坐标为i1

的点只能由它上面和左边的点得到，而这两个点满足其中一个横坐标为i1 - 1，另一个纵坐标为j1 -

1（如果j是合法的话，什么是合法的，代码中会给出解释）i2点同理，所以一个状态可以分为4个子

状态，并且这四个子状态的横纵坐标之和都是k - 1.

代码实现：

1. #include
2. #include
3. #include
6. using namespace std;
7. const int N = 15;
8. int g[N][N], f[N + N][N][N], n;//横纵左边之和的值的最大值为2N
10. int main()
11. {
12. scanf("%d", &n);
14. int a, b, c;
15. while(cin >> a >> b >> c, a || b || c) g[a][b] = c;//a,b,c同时为零时停止输入
17. for(int k = 2; k <= n + n; k++)//起点横纵坐标之和为2，所以k从2开始到2n
18. for(int i1 = 1; i1 <= n; i1++)
19. for(int i2 = 1; i2 <= n; i2++)
20. {
21. int j1 = k - i1;
22. int j2 = k - i2;
24. //k是从2开始递增的，而i1显然可以取到一个大于2的数，此时的j1就会是一个不在
25. //1~n范围内的数，这样的j就是不合法的，所以我们再计算状态的时候，需要
26. //对j的合法性进行判断，否则会sf。
27. if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
28. {
29. int t = g[i1][j1];
30. if(i1 != i2) t += g[i2][j2];
32. int &x = f[k][i1][i2];
33. //第一个状态表示两个子点都是i1，i2左边的点。
34. x = max(x, f[k - 1][i1][i2] + t);
35. //第二个状态表示一个在上面，另一个在左边。
36. x = max(x, f[k - 1][i1 - 1][i2] + t);
37. //与二同理，只不过两个点顺序换了
38. x = max(x, f[k - 1][i1][i2 - 1] + t);
39. //两个点都在上边。
40. x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
41. }
43. }
45. printf("%d", f[n + n][n][n]);//到终点的最大值。
46. return 0;
47. }

T5:acwing275

题目描述：

小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。

一次素质拓展活动中，班上同学安排坐成一个 m 行 n 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。

幸运的是，他们可以通过传纸条来进行交流。

纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标 (1,1)(1,1)，小轩坐在矩阵的右下角，坐标 (m,n)。

从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。 

在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。

班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙，反之亦然。 

还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用 00 表示），可以用一个 0∼1000∼100 的自然数来表示，数越大表示越好心。

小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。

现在，请你帮助小渊和小轩找到这样的两条路径。

输入：

输入格式

第一行有 22 个用空格隔开的整数 m 和 n，表示学生矩阵有 m 行 n 列。

接下来的 m 行是一个 m×n 的矩阵，矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度，每行的 n个整数之间用空格隔开。

状态分析：这题同样可以用f[2N][N][N]（各元素含义和上一题相同来表示），有区别的地方在于，每个点只能走一次，比如第一个运动走过了点（k，j）第二个运动就没法经过这个点了，所以我们需要对每个点只能走一次这个特点处理。

实际上我们可以证明，从起点（1，1）走到终点（n，n）的所有路径中经过的点的值最大的方案（此题中为“好心程度之和”）一定是两条没有交点的路径。

Prove:我们采用反证法，证明所有有交点的路径一定能被优化为没有交点的路径

 

 如上图，st，ed分别代表起终点（图拿鼠标画的（）），红色和黑色分别为两次运动的路径，显然这个时候有很多交点，那么我们发现这个图（运动路径）实际可以等效成下图的情况（situation）

 即黑色的路径和红色的路径各处一边，那么这种情况实际上并不是最优解，比如点（2，2）就是第一个红黑路径的交点，可以变成黑色路径先走（1，3）再走到（3，1），原因在于：当红黑路径交于（2，2）时，这个点上的值只能被计算一次，因此另一次的经过这个点便显得没有意义了，所以我们绕过这个点的同时，这个点的值不仅能被计算，还能计算其余更多点的值。

所以我们可以套用上一题代码。证明完毕（） 

代码：

1. #include
2. #include
3. #include
6. using namespace std;
7. const int N = 55;
8. int g[N][N], f[N + N][N][N];
10. int main()
11. {
12. int n, m;
13. scanf("%d%d", &n, &m);
15. for(int i = 1; i <= n; i++)
16. for(int j = 1; j <= m; j++) scanf("%d", &g[i][j]);
18. for(int k = 2; k <= n + m; k++)
19. for(int i1 = 1; i1 <= n; i1++)
20. for(int i2 = 1; i2 <= n; i2++)
21. {
22. int j1 = k - i1;
23. int j2 = k - i2;
25. if(j1 >= 1 && j1 <= m && j2 >=1 && j2 <= m)
26. {
27. int t = g[i1][j1];
28. if(i1 != i2) t += g[i2][j2];
30. int &x = f[k][i1][i2];
31. x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
32. x = max(x, f[k - 1][i1 - 1][i2] + t);
33. x = max(x, f[k - 1][i1][i2 - 1] + t);
34. x = max(x, f[k - 1][i1][i2] + t);
35. }
36. }
38. printf("%d", f[n + m][n][n]);
39. return 0;
40. }

---------------------------------------------------------------end-------------------------------------------------------------