前言:多總結(jié), 多學(xué)習(xí)
0X00 基本模型
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 題目變形
矩形
這個(gè)變形就很簡(jiǎn)單了, 直接上答案
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])
同上, 變矩形以及最大值變?yōu)樽钚≈?/p>
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])
兩遍
兩遍遍歷的方法就是同時(shí)更新兩個(gè)人
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] 的實(shí)際含義
k 其實(shí)就是矩形的斜邊, 按這樣遍歷一定能把這個(gè)矩形遍歷完
dp[k][i1][i2] 就是圖上橙色兩點(diǎn)的合, 更新的方法 就是圖上兩點(diǎn)上邊和左邊的兩點(diǎn)也就是四個(gè)點(diǎn)
正反走
正反走的本質(zhì)就是走兩遍,因?yàn)榱硗庖槐榉粗鴣砭褪欠粗?/p>
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())
# 動(dòng)態(tài)規(guī)劃
dp = [[[0]*(m+1)for _ in range(m+1)] for _ in range(m+n + 1)]
# 保證二者不會(huì)重合, 但是又能把整個(gè)矩陣遍歷完
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])
里面用到一個(gè)小技巧就是始終不讓兩點(diǎn)重合
正反走且有的地方不能走
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]
注意有的地方不能走要用「特?cái)?shù)值標(biāo)注一下」
因此一定要注意初始化!!!!
