M02760: 数字三角形

dp, dfs, http://cs101.openjudge.cn/practice/02760

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

      (图1)

图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

输入

输入的是一行是一个整数N (1 < N ≤ 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。

输出

输出最大的和。

样例输入

样例输出

来源：翻译自 IOI 1994 的试题

要求自底向上DP实现一次，递归+记忆化搜索实现一次

2020fall-cs101，蓝克轩。

dp方法：用2d list记录三角形，然后从倒数第二排开始更改，将每个数改成下面两个可以加上的数的最大和，就能往上推出最大路径。

python

n = int(input())
tri = []   # triangle

for i in range(n):
    tri.append(list(map(int, input().split()))+[0 for j in range(n-i-1)])

for i in range(n-2,-1,-1):
    for j in range(i+1):
        tri[i][j] += max(tri[i+1][j], tri[i+1][j+1])

print(tri[0][0])

递归+记忆化搜索

python

from functools import lru_cache

n = int(input())
triangle = [list(map(int, input().split())) for _ in range(n)]

@lru_cache(None)
def dfs(i, j):
    if i == n - 1:   # 到底层
        return triangle[i][j]
    return triangle[i][j] + max(dfs(i + 1, j), dfs(i + 1, j + 1))

print(dfs(0, 0))

2020fall-cs101，李嘉钰。

解题思路：从三角形的最底层开始往上走，相邻的两个数字只有值较大者可以向上走，并且和上层的数字结合，值较小者被淘汰。最后，在三角形顶端的数字就是所有路径中的最大和。

python

n = int(input())
tri = []   # triangle

for i in range(n):    
    tri.append([int(x) for x in input().split()])

for i in range(n-1, 0, -1):    
    for x in range(len(tri[i-1])):        
        tri[i-1][x] = max(tri[i-1][x] + tri[i][x], tri[i-1][x] + tri[i][x+1])

print(tri[0][0])

2020fall-cs101，阚立言

解题思路：从上往下Top-down。

python

n = int(input())
tri = [[0]+[int(_) for _ in input().split()]+[0] for i in range(n)]
for i in range(1,n):
        for key in range(1,i+2):
                tri[i][key] += max(tri[i-1][key-1], tri[i-1][key])
print(max(tri[n-1]))

2020fall-cs101，孙湛劼

显然贪心是行不通的，所以考虑 dp。记 $S_{i, j}$ 为以第 $ (𝑖,𝑗)$ 位置的元素结尾的路径的和的最大值，那么对一个 $ (𝑖,𝑗)$ 位置的数，他可以接在 $(𝑖 - 1, 𝑗 - 1)$ 和 $(𝑖 - 1, 𝑗)$ 的后面，那么就得到了 dp方程 $𝑆_{𝑖, 𝑗} = m a x {𝑆_{𝑖 - 1, 𝑗 - 1}, 𝑆_{𝑖 - 1, 𝑗}} + 𝑎_{𝑖, 𝑗}$

python

N = int (input())
S = []
for i in range (N):    
    S.append([int (x) for x in input().split()])
    
ans = [[S[0][0]]]
for i in range (1,N):    
    SS = []
    for j in range (i+1):
        if j==0:            
            SS.append(ans[i-1][0]+S[i][0])
        if 1<=j<=i-1:            
            SS.append(max(ans[i-1][j-1],ans[i-1][j])+S[i][j])
        if j==i:            
            SS.append(ans[i-1][i-1]+S[i][j])    
    ans.append(SS.copy())
    
print (max(ans[N-1]))

dp+dfs方法

python

n = int(input())

node = []
node.append( [-1 for _ in range(n+2)] )
for _ in range(n):
    tmp = [int(_) for _ in input().split()]
    node.append([-1] +tmp + [-1]*(n - len(tmp)) + [-1])
    
node.append( [-1 for _ in range(n+2)] )

opt = [[0]*(n+2) for _ in range(n+2)]

def dp(i,j):
    if opt[i][j]>0:
        return opt[i][j]
    
    if node[i+1][j]==-1 or node[i+1][j+1]==-1 :
        return node[i][j]
    
    opt[i][j] = node[i][j] + max( dp(i+1, j), dp(i+1, j+1) )
    return opt[i][j]

ans = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        ans = max( ans, dp(i,j) )

print(ans)

2020fall-cs101，章斯岚。这种题目尽量不用二维数组可以使代码简化。直接开一个一维数组就可以解决存储问题（每一层存储后都可以丢弃）

python

a = []
dp = [0]*102
for i in range(int(input())):
    a.append(list(map(int,input().split())))
a = a[::-1] 
for i in a:
    for j in range(len(i)):
        dp[j] = max(dp[j+1], dp[j]) +i[j]
print(dp[0])

M02760: 数字三角形 ​

M02760: 数字三角形