Lunski's Clutter

This is a place to put my clutters, no matter you like it or not, welcome here.

0%

2D Dynamic Programming

二維動態規劃用轉移矩陣分析。

Bottom-Up每隔是右與下加總取第一格,採用Top-Down寫法就是左與上的轉移方程式,取最後一格,因為要加總,起始為0。
img

i, j符合可以向右下走,不合看右或下
img

C跟B不合看右或下
右: e 跟bcde比
下: c 跟cde比
3表示有3個符合
img

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n, m = len(text1), len(text2)

M = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n-1, -1, -1):
for j in range(m-1, -1, -1):
if text1[i] == text2[j]:
M[i][j] = M[i+1][j+1] + 1
else:
M[i][j] = max(M[i][j+1], M[i+1][j])
return M[0][0]

多重選取幣值,要到目標價格。
最右 1, 1, 1,從右下角填表至左上角,每點看右與下加總,左上角是結果,用採用Top-Down寫法
img

1
2
3
4
5
6
7
8
9
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]

return dp[-1]

Image Credits: Neetcode


如果你覺得這篇文章很棒,請你不吝點讚 (゚∀゚)

Welcome to my other publishing channels