题目描述
解题思路
可以从上到下考虑,也可以考虑从上到下
-
从上到下考虑的时候,会考虑一些边界问题:就是在这一点要考虑他是从左边下来还是从右边下来,那么每行的两边都要考虑一个边界问题
-
从下到上会少一些边界判定,在这点判断是从左边还是右边上来,这里竟然不用考虑边界了!
DP问题
算法1
动态规划 $O(n^2)$
n = int(input())
li = []
for i in range(n):
li.append(list(map(int, input().split())))
for i in range(n-2,-1,-1): #逆序range
for j in range(len(li[i])):
li[i][j] += max(li[i+1][j], li[i+1][j+1])
print(li[0][0])