数字三角形模型

前言:多总结, 多学习

0X00 基本模型

• 120. 三角形最小路径和

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        if len(triangle) == 0: return 0
        m, n = len(triangle), len(triangle)

        dp = [[float("inf")] * (n+1) for _ in range(m+1)]
        dp[0][0] = 0

        for x in range(1, m+1):
            for y in range(1, x+1):
                dp[x][y] = min(dp[x-1][y-1], dp[x-1][y]) + triangle[x-1][y-1]
        
        return min(dp[m])

0X01 题目变形

矩形

1015. 摘花生

这个变形就很简单了, 直接上答案

T = int(input())
for _ in range(T):
    m, n = map(int, input().split())
    mat = [[0] * (n+1) for _ in range(m+1)]
    for x in range(1, m+1):
        mat[x][1:] = map(int, input().split())
    
    dp = [[0] * (n+1) for _ in range(m+1)]
    for x in range(1, m+1):
        for y in range(1, n+1):
            t = mat[x][y]
            dp[x][y] = max(dp[x-1][y] + t, dp[x][y-1] + t, dp[x][y])
    
    print(dp[m][n])

1018. 最低通行费

同上, 变矩形以及最大值变为最小值

m = n = int(input())
mat = [[0] * (n+1) for _ in range(m+1)]
for x in range(1, m+1):
    mat[x][1:] = map(int, input().split())

dp = [[float("inf")] * (n+1) for _ in range(m+1)]

for x in range(1, m+1):
    for y in range(1, n+1):
        t = mat[x][y]
        if x == y == 1: 
            dp[x][y] = t
        else:
            dp[x][y] = min(dp[x-1][y], dp[x][y-1]) + t

print(dp[m][n])

两遍

1027. 方格取数

两遍遍历的方法就是同时更新两个人

n = int(input())
mat = [[0] * (n+1) for _ in range(n+1)]

while True:
    x, y, v = map(int, input().split())
    if x == y == v == 0: break
    mat[x][y] = v

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

for k in range(2, 2*n+1):
    for x1 in range(1, n+1):
        for x2 in range(1, n+1):
            y1, y2 = k - x1, k - x2
            if y1 < 0 or y2 < 0 or y1 > n or y2 > n: continue
            t = mat[x1][y1]
            if x1 != x2:
                t += mat[x2][y2]
            dp[k][x1][x2] = max(dp[k-1][x1][x2], dp[k-1][x1-1][x2], dp[k-1][x1][x2-1], dp[k-1][x1-1][x2-1]) + t

print(dp[2*n][n][n])

首先我们讨论一下这里 dp[k][i1][i2] 的实际含义

k 其实就是矩形的斜边, 按这样遍历一定能把这个矩形遍历完

dp[k][i1][i2] 就是图上橙色两点的合, 更新的方法 就是图上两点上边和左边的两点也就是四个点

正反走

275. 传纸条

正反走的本质就是走两遍,因为另外一遍反着来就是反着走

m, n = map(int, input().split())

mat = [[0] * (n+1) for _ in range(m+1)]

for x in range(1, m+1):
    mat[x][1:] = map(int, input().split())

# 动态规划
dp = [[[0]*(m+1)for _ in range(m+1)] for _ in range(m+n + 1)]

# 保证二者不会重合, 但是又能把整个矩阵遍历完
for k in range(2, m + n + 1):
    for x1 in range(1, min(k, m+1)):
        for x2 in range(1, x1):
            y1, y2 = k - x1, k - x2
            if y1 <= 0 or y2 <= 0 or y1 > n or y2 > n: continue
            t = mat[x1][y1] + mat[x2][y2]             
            dp[k][x1][x2] = max(dp[k-1][x1][x2], dp[k-1][x1-1][x2], dp[k-1][x1][x2-1], dp[k-1][x1-1][x2-1]) + t
            

print(dp[m+n-1][m][m-1])

里面用到一个小技巧就是始终不让两点重合

正反走且有的地方不能走

741. 摘樱桃

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        if len(grid) == 0: return 0
        m, n = len(grid), len(grid[0])
        dp = [[[float("-inf")] * (m+1) for _ in range(m+1)] for _ in range(m+n+1)]
        dp[1][0][1] = dp[1][1][0] = 0
        for k in range(2, m+n+1):
            for x1 in range(1, min(m+1, k)):
                for x2 in range(1, x1+1):
                    y1, y2 = k -  x1, k - x2
                    if y1 <= 0 or y2 <= 0 or y1 > n or y2 > n: continue
                    if min(grid[x1-1][y1-1], grid[x2-1][y2-1]) == -1: continue

                    t = grid[x1-1][y1-1]
                    if x1 != x2:
                        t += grid[x2-1][y2-1]
                        
                    dp[k][x1][x2] = max(dp[k-1][x1][x2], dp[k-1][x1-1][x2], dp[k-1][x1][x2-1], dp[k-1][x1-1][x2-1]) + t
        
        return 0 if dp[m+n][m][m] == float("-inf") else dp[k][x1][x2]

注意有的地方不能走要用「特数值标注一下」

因此一定要注意初始化!!!!