一道蓝桥杯的动态规划练习题: 历届试题 数字三角形：
“上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
路径上的每一步只能从一 个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过1。”
解题思路：
先不考虑左右路径选择次数相差不超过1的约束，就是一个简单的动态规划
根据输入的三角形大小n，定义一个大小n * n的状态数组dp:
dp = [[0] * n for _ in range(n)]
那么对应的状态转移方程为：
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
其中dp[i][j]表示为从顶点开始，走到第i行j列时能够得到的最大路径和，如图：
状态转移过程
红色问好
?处的值，如果是取左上（意味着这条路径是从左上到右下）的话，值是10 + 1 = 11，而如果是取右上的话，值就是15 + 1 = 16，显然是取右上。需要注意的地方是，题目的三角形是金字塔式的正三角形，但是放到矩阵里面就是向左歪的。
完整代码为：
# -*- coding: utf-8 -*-
import io
import sys
def cal():
n = int(input())
triangle = []
for _ in range(n):
triangle.append(list(map(int, input().split())))
dp = [[0] * n for _ in range(n)]
dp[0][0] = triangle[0][0]
for i in range(1, n):
for j in range(i + 1):
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
return max(dp[-1])
def test():
sys.stdin = io.StringIO('''5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5''')
assert 30 == cal()
if __name__ == '__main__':
test()
dp数组填充结果：
#triangle
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
#dp
7 0 0 0 0
10 15 0 0 0
18 16 15 0 0
20 25 20 19 0
24 30 27 26 24
dp数组最后一行24 30 27 26 24已经有我们的目标结果27了，但是我们直接使用return max(dp[-1])只会得到30，所以需要添加左右路径选择次数相差不超过1的约束。也即是需要记录下路径的选择过程，然后在24 30 27 26 24中选择最后满足约束的值里面的最值。
为记录路径选择情况，添加一个path数组，但是我们并不需要完整的记录路径的具体选择情况来回溯出整个路径，而是只需要记录到某个节点所选择的路径中，选择左边的次数和选右边的次数的差值即可：
path = [[0] * n for _ in range(n)]
定义如果是选择右边的话，那么path值就减一，如果是左边的话，值加一：
path状态
对于三角形里面值
8对应的path值计算过程是：由于到8只能是右走，所以值为-1对于三角形里面值
1对应的path值计算过程是：由于dp数组在选择的时候，11 < 16选择了右边的路径，那么path的值应该为-1加上1，为-1 + 1 = 0。
那么满足约束条件的值对应的abs(path[i][j])应该小于等于1。
添加path之后：
import io
import sys
def cal():
n = int(input())
triangle = []
for _ in range(n):
triangle.append(list(map(int, input().split())))
dp = [[0] * n for _ in range(n)]
dp[0][0] = triangle[0][0]
path = [[0] * n for _ in range(n)]
for i in range(1, n):
for j in range(i + 1):
dp[i][j] += triangle[i][j]
if dp[i - 1][j - 1] > dp[i - 1][j]:
path[i][j] = path[i - 1][j - 1] - 1
dp[i][j] += dp[i - 1][j - 1]
else:
path[i][j] = path[i - 1][j] + 1
dp[i][j] += dp[i - 1][j]
ans = 0
for i in range(n):
if abs(path[-1][i]) <= 1:
ans = max(ans, dp[-1][i])
return ans
def test():
sys.stdin = io.StringIO('''5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5''')
assert 27 == cal()
if __name__ == '__main__':
test()
path数组填充结果：
0 0 0 0 0
1 -1 0 0 0
2 0 -2 0 0
3 1 -1 -3 0
4 2 0 -2 -4
显然根据path数组最后的结果4 2 0 -2 -4只有第三个值为0，对应dp数组中的24 30 27 26 24第三个值27就是我们想要的答案，此时的路径为：7-3(左)-8(左)-7(右)-2(右)
完整测试代码：
# -*- coding: utf-8 -*-
import io
import sys
def cal():
n = int(input())
triangle = []
for _ in range(n):
triangle.append(list(map(int, input().split())))
dp = [[0] * n for _ in range(n)]
dp[0][0] = triangle[0][0]
path = [[0] * n for _ in range(n)]
for i in range(1, n):
for j in range(i + 1):
dp[i][j] += triangle[i][j]
if dp[i - 1][j - 1] > dp[i - 1][j]:
path[i][j] = path[i - 1][j - 1] - 1
dp[i][j] += dp[i - 1][j - 1]
else:
path[i][j] = path[i - 1][j] + 1
dp[i][j] += dp[i - 1][j]
ans = 0
for i in range(n):
if abs(path[-1][i]) <= 1:
ans = max(ans, dp[-1][i])
return ans
def test():
sys.stdin = io.StringIO('''15
3
3 4
7 1 9
6 9 9 0
6 1 1 6 0
0 4 8 2 0 9
9 3 5 3 8 5 8
9 5 7 2 8 1 9 1
0 8 3 1 8 9 5 9 7
5 9 3 5 3 3 5 4 8 0
7 6 5 7 7 2 6 0 2 7 1
5 9 9 0 0 7 9 5 8 8 2 9
3 0 4 6 5 8 6 5 7 3 2 4 0
6 0 2 0 9 6 7 8 7 8 1 7 9 8
7 0 3 7 3 3 3 2 8 4 8 5 1 1 9''')
assert 94 == cal()
sys.stdin = io.StringIO('''50
11
22 17
18 21 44
19 6 4 36
45 31 31 38 11
34 25 26 25 8 42
12 8 28 19 1 1 1
18 8 2 29 31 19 0 4
15 19 12 21 7 7 2 38 47
14 25 23 42 0 33 37 15 43 17
34 46 18 38 14 29 40 46 12 11 48
16 26 19 28 0 26 37 2 14 35 18 41
10 13 42 43 2 7 39 19 43 35 39 31 2
20 23 48 32 36 48 0 13 17 28 13 45 18 17
11 5 38 3 15 3 47 10 5 6 49 26 49 35 17
33 37 38 6 37 20 45 37 21 10 4 1 25 49 19 42
10 26 32 15 41 35 12 4 42 18 3 18 18 40 36 1 29
24 9 18 46 6 5 17 16 11 21 41 12 42 36 25 19 18 40
12 4 3 16 46 21 22 17 41 14 3 44 44 29 6 14 25 12 22
45 29 33 16 20 46 8 6 21 29 27 11 42 31 16 8 29 38 32 48
31 47 3 26 43 32 32 9 10 44 31 7 23 15 23 46 13 33 2 34 13
29 47 7 12 14 17 44 4 0 42 35 49 48 11 42 30 45 1 42 40 35 49
15 0 24 11 13 8 16 49 23 47 46 30 12 12 47 8 16 49 2 4 48 0 15
42 31 13 46 25 3 31 25 20 31 49 32 46 9 0 47 32 49 43 14 11 8 12 19
26 13 22 30 12 22 48 4 5 11 0 31 14 31 8 36 14 7 18 12 17 20 9 1 20
5 16 31 15 30 3 41 43 27 22 5 49 22 12 7 33 12 40 49 46 48 35 12 5 6 27
24 26 38 26 46 43 42 30 8 22 35 2 15 12 24 23 13 46 35 20 31 49 10 30 47 8 17
12 16 23 39 40 2 27 16 0 23 10 32 33 32 17 35 0 29 11 25 45 9 12 15 40 13 28 22
11 38 40 25 4 15 14 47 17 43 13 20 18 24 2 2 8 20 39 10 1 1 35 46 10 49 14 3 13
42 25 26 30 17 1 37 35 17 34 2 10 49 22 31 25 27 35 34 47 24 46 0 27 34 47 38 33 11 43
46 5 20 22 37 38 23 24 25 40 10 27 3 10 2 36 35 31 21 21 28 45 20 28 25 4 27 13 37 38 8
34 43 28 8 31 18 34 7 43 24 18 23 29 30 27 15 17 8 38 41 38 36 11 16 11 15 46 26 2 34 34 38
30 14 49 13 33 33 20 28 9 40 1 41 20 30 8 38 38 47 29 26 33 42 45 44 7 41 22 11 27 6 0 7 20
1 22 5 34 43 34 43 33 37 34 6 18 43 46 8 42 27 37 25 19 32 21 26 25 43 39 4 1 41 14 23 42 36 29
26 31 15 22 17 2 6 23 22 1 19 31 43 48 18 20 17 2 43 45 29 38 34 33 39 26 47 13 18 36 44 47 17 9 19
34 11 27 9 34 31 30 15 26 28 35 47 45 37 42 42 16 31 27 1 22 5 49 35 23 35 29 22 4 38 41 39 2 19 0 38
2 31 3 28 9 40 27 7 27 20 1 45 3 28 46 25 33 47 13 9 32 44 31 39 35 25 30 37 46 30 25 48 11 30 26 23 22
6 32 49 26 33 46 31 14 42 8 49 40 21 8 24 18 42 15 3 17 45 42 15 26 19 13 39 1 41 14 23 47 46 24 25 32 20 6
46 14 15 47 6 38 6 31 6 0 48 9 19 44 1 34 20 22 47 11 23 40 26 46 38 24 20 13 6 40 20 4 7 37 2 13 25 10 46
32 10 45 43 31 39 47 15 11 19 14 22 43 4 48 39 42 23 12 8 31 4 28 36 11 15 40 25 42 0 21 24 12 16 18 43 7 15 10 18
36 24 41 29 30 39 21 23 14 35 31 48 39 11 34 1 28 26 28 20 28 49 45 40 18 15 35 25 32 45 44 18 21 37 0 1 28 23 26 43 8
7 41 47 20 27 0 48 5 28 21 33 30 16 23 0 33 8 25 17 5 21 35 26 10 37 27 39 10 4 34 18 13 27 18 36 4 20 36 11 49 7 44
31 25 19 31 8 29 8 25 34 32 13 12 42 2 41 31 13 47 15 33 11 42 3 49 48 24 35 9 25 43 5 6 18 24 39 29 3 47 6 37 29 21 49
24 24 41 7 39 38 23 24 1 17 30 2 18 4 38 29 31 33 35 37 1 9 26 32 15 25 39 2 7 10 4 31 36 47 40 27 37 13 2 41 33 32 43 3
38 33 32 19 16 19 8 20 31 36 2 46 11 41 0 20 4 6 3 42 3 44 20 43 9 22 36 42 6 29 45 44 13 30 13 31 49 21 1 30 9 4 26 20 47
29 43 3 35 46 46 41 40 16 36 2 40 22 44 46 3 42 42 16 22 7 0 23 30 1 4 39 5 32 11 5 11 4 8 49 1 4 42 43 22 28 45 12 0 42 10
3 34 4 22 8 11 24 31 41 25 35 30 33 20 42 38 33 48 46 32 49 3 26 45 27 4 40 40 6 32 2 12 18 7 36 26 20 10 8 12 37 45 44 20 15 38 8
1 37 7 35 38 12 12 33 39 18 26 31 25 10 36 39 29 43 25 7 15 37 17 27 24 13 24 45 30 12 5 33 1 14 19 40 26 31 25 18 49 1 49 26 14 35 15 43
30 40 2 46 29 20 25 4 35 49 1 15 14 6 1 17 23 20 9 1 3 35 19 2 38 21 31 2 8 46 47 41 39 0 39 18 20 14 24 5 16 25 22 32 34 23 1 7 45
11 8 48 48 30 3 38 1 34 43 11 30 40 2 21 42 41 40 14 8 16 21 24 42 46 8 26 21 9 33 17 20 43 15 20 23 18 9 24 4 2 36 35 44 40 8 37 32 0 1''')
assert 1736 == cal()
if __name__ == '__main__':
test()
网友评论