动态规划入门（数字三角形模型）

备战2024年蓝桥杯&算法学习 -- 每日一题
Python大学A组

        试题一：摘花生
        试题二：最低通行费用
        试题三：方格取数
        试题四：传纸条

---

试题一：摘花生

【题目描述】

        Hello Kitty想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。Hello Kitty只能向东或向南走，不能向西或向北走。问Hello Kitty最多能够摘到多少颗花生。

【输入格式】

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

        接下来是T组数据。

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

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

【输出格式】

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

【数据范围】

        1≤T≤100,
        1≤R,C≤100,
        0≤M≤1000

【输入样例】

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

【输出样例】

8
16

【解题思路】

        线性DP中的数字三角形模型，基础模型，状态转移方程f[i][j] = max(f[i-1][j] , f[i][j-1]) + w[i][j]。

【Python程序代码】

T = int(input())
for _ in range(T):
    r,c = map(int,input().split())
    a = [[0]*(c+5)]
    for i in range(r):
        a.append([0]+list(map(int,input().split())))
    f = [[0]*(c+5) for _ in range(r+5)]
    for i in range(1,r+1):
        for j in range(1,c+1):
            f[i][j] = max(f[i-1][j],f[i][j-1])+a[i][j]
    print(f[r][c])

---

试题二：最低通行费用

【题目描述】

        本题大意上给定一个 n×n的矩阵，让我们从左上角出发，最终走到右下角走过的方块数量的不能超过 2n−1个求所有路线中，经过的方块的总价值最少的路线。

【解题思路】

        和上一题相比改了一些条件，比如增加了一个不能超过2n-1个方块，考虑一下（1，1）到（n，n）的曼哈顿距离发现d = 2*n-2，同时题目要求的是求总价值最小，在2*n-2的最短路径上加上一个方块一定会大于等于这2*n-2个方块的价值，所以本题可以套上面题目的板子。

【Python程序代码】

n = int(input())
f = [[1e9]*(n+5) for _ in range(n+5)]
a = [[0]*(n+5)]
for i in range(n):
    a.append([0]+list(map(int,input().split())))
f[0][1]=f[1][0]=0
for i in range(1,n+1):
    for j in range(1,n+1):
        f[i][j] = min(f[i][j-1],f[i-1][j])+a[i][j]
print(f[n][n])

---

试题三：方格取数

【题目描述】

        设有N×N 的方格图(N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0。如下图所示（见样例）:

         某人从图的左上角的 A 点出发，可以向下行走，也可以向右走，直到到达右下角的 B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 0）。
        此人从 A 点到 B 点共走两次，试找出 2 条这样的路径，使得取得的数之和为最大。

【输入数据】

        输入的第一行为一个整数 N（表示 N×N 的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的 0 表示输入结束。

【输出数据】

        只需输出一个整数，表示 2 条路径上取得的最大的和。

【输入样例】

8
2 3 13
2 6  6
3 5  7
4 4 14
5 2 21
5 6  4
6 3 15
7 2 14
0 0  0

【输出样例】

67

【解题思路】

        需要考虑两条路径，如何考虑更好呢？如果说分别考虑的话如何判断是否重合呢且这两者相加也不一定是最大值，所以如果能够同时考虑两条路就好了，首先两条路的曼哈顿距离一定是相等的，所以我们可以考虑枚举每一条路径走的行的数量，列的数量可以用曼哈顿距离-列的数量，所以f[k][i][j]表示曼哈顿距离为k，且第一条路径走了i行k-i列，第二条路径走了j行k-j列，那么如何考虑状态转移呢？每一个f[k][i][j]可以由第一条路径往右走或者往下走过来，也即使f[k-1][i][j]和f[k-1][i-1][j]，第二条路径也是往右或往下，f[k-1][i][j]，f[k-1][i][j-1]，那也就是四种状态：f[k-1][i-1][j-1]、f[k-1][i][j-1]、f[k-1][i-1][j]、f[k-1][i][j]。

【Python程序代码】

n = int(input())
w = [[0]*(n+5) for _ in range(n+5)]
a,b,c = map(int,input().split())
while not (a==0 and b==0 and c==0):
    w[a][b] += c
    a, b, c = map(int, input().split())
f = [[[0]*(n+5) for _ in range(n+5)] for i in range(2*n+5)]
for k in range(2,2*n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if k-i<=0 or k-j<=0 or k-i>n or k-j>n:continue
            v = w[i][k-i]
            t = f[k][i][j]
            if i!=j:v+=w[j][k-j]
            t = max(t, f[k-1][i-1][j-1])
            t = max(t, f[k-1][i][j-1])
            t = max(t, f[k-1][i-1][j])
            t = max(t, f[k-1][i][j])
            f[k][i][j] = t+v
print(f[2*n][n][n])

---

试题四：传纸条

【题目描述】

        小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排坐成一个 m 行 n 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标 (1,1)，小轩坐在矩阵的右下角，坐标 (m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。 在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙，反之亦然。 还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用 0 表示），可以用一个 0∼100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。现在，请你帮助小渊和小轩找到这样的两条路径。

【输入格式】

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

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

【输出格式】

        输出一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

 【数据范围】

        1≤n,m≤50

【输入样例】

3 3
0 3 9
2 8 5
5 7 0

【输出样例】

34

【解题思路】

        和上面一题类似，多了一个路径不可重复，考虑一下用上面的方法做一下得到两条路径，如果路径没有交叉和重叠点那么上面的就是答案。如果有交叉呢。

        对于有交叉的我们可以通过移动变到没有交叉但是个别点重合。对于重复，我们必然可以在两条路线中找到额外的一条或两条路线，使得新的路线不发生重合。如下图：

        由于原路线是最优解，则必然 wA=wB=0，否则最优解路径必然是经过A或B的，因此，我们可以通过微调其中的一条路线，使之不经过重合点 C，同时路线的总价值没有减少。所以可以直接用方格取数的方法。

【Python程序代码】

n,m = map(int,input().split())
a = [[0]*(m+5)]
for i in range(n):
    a.append([0]+list(map(int,input().split())))
f = [[[0]*(n+5) for i in range(n+5)] for j in range(n+m+5)]
for k in range(2,n+m+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if k-i>m or k-i<=0 or k-j>m or k-j<=0:continue
            t = f[k][i][j]
            v = a[i][k-i]
            if i!=j:v+=a[j][k-j]
            t = max(t, f[k-1][i-1][j-1])
            t = max(t, f[k-1][i-1][j])
            t = max(t, f[k-1][i][j-1])
            t = max(t, f[k-1][i][j])
            f[k][i][j] = t+v
print(f[n+m][n][n])