下面的例子不錯：?對于動態規劃，能學到不少東西；

你要清楚每一步都在做什么，劃分細致就能夠拆解清楚！

?xk. - 力扣（LeetCode）

labuladong的算法筆記-動態規劃-CSDN博客

動態規劃是一種強大的算法設計策略，用于解決具有重疊子問題和最優子結構特點的問題。在面對動態規劃類題目時，遵循以下步驟可以幫助你系統地解決問題：

1. 定義狀態

• 確定變量：識別哪些變量會影響問題的解。例如，在背包問題中，關鍵變量可能是物品的重量和價值，以及剩余的背包容量。
• 狀態表示：用這些變量定義狀態。例如，dp[i][w]?可能表示前i個物品放入容量為w的背包所能獲得的最大價值。

2. 狀態轉移方程

• 建立關系：找到狀態之間的關系，即如何從一個狀態轉移到另一個狀態。這通常涉及到一個遞推公式。例如，在斐波那契數列中，F(n) = F(n-1) + F(n-2)。
• 邊界條件：確定遞推公式的起始狀態，通常是最簡單的情況，例如?dp[0][w] = 0（背包問題中沒有物品時的價值）。

3. 選擇方向

• 自底向上：從最簡單的狀態開始，逐步構建更復雜的狀態。這種方法通常使用循環實現，避免了重復計算。
• 自頂向下：從復雜的狀態開始，遞歸地解決子問題。這種方法通常使用遞歸和記憶化（memoization）來避免重復計算。

4. 初始化

• 初始狀態：根據問題的性質初始化DP數組。例如，所有狀態初始化為0或無窮大。

5. 計算

• 填充DP表：根據狀態轉移方程填充DP表或數組。確保按正確的順序填充，以便在計算每個狀態時，所需的前驅狀態已經被計算。

6. 返回結果

• 解析答案：DP過程完成后，根據問題要求解析出最終答案。這可能是DP表中的某個特定值，也可能是回溯整個DP過程找到最優解的具體方案。

7. 復雜度分析

• 時間復雜度：通常由狀態的數量和狀態轉移的復雜度決定。
• 空間復雜度：由存儲狀態所需的空間決定，可以通過滾動數組等方式優化空間復雜度。

1 70. 爬樓梯

假設你正在爬樓梯。需要?n?階你才能到達樓頂。

每次你可以爬?1?或?2?個臺階。你有多少種不同的方法可以爬到樓頂呢？

示例 1：

輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階

這是一個簡單的動態規劃的問題：

分解問題：不積硅步無以至千里！

假設：當前到了第x層,并且小于x層的走法f(x)我們都知道。

那么后面如何求呢？

1. 第一個階梯、第二個階梯都是1下就能走到！
2. y = x+1,那么 f（y） = f(y-1) + f(y-2), 想要上到第y步， 一定是從前面階梯走過來的。

class Solution:def climbStairs(self, n: int) -> int:dp = [1] * (n+1)for i in range(2,n+1):dp[i] = dp[i-1] + dp[i-2]#print(dp)return dp[n]

2?198. 打家劫舍?

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你?不觸動警報裝置的情況下?，一夜之內能夠偷竊到的最高金額。

相鄰不能同時偷！

示例 1：

輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。偷竊到的最高金額 = 1 + 3 = 4 。

在做這一個題目的時候：

f(x):?到第x個房間能得到的最大收益；

我也是設定：加入到了第X個房間，那么之前的狀態（到房間能得到的最大收益）我都是知道的。所以，f(X+1) 怎么做才能最大呢？

怎么能偷到x+1個房子，由x-1過來的，x-2過來的（開始我沒考慮到這點）。

class Solution:def rob(self, nums: List[int]) -> int:dp = nums[::]for i in range(2,len(nums)):temp = dp[i-2]if i-3>=0:temp = max(temp,dp[i-3])dp[i] = temp + nums[i]return max(dp)

3?322. 零錢兌換

給你一個整數數組?coins?，表示不同面額的硬幣；以及一個整數?amount?，表示總金額。

計算并返回可以湊成總金額所需的?最少的硬幣個數?。如果沒有任何一種硬幣組合能組成總金額，返回?-1?。

你可以認為每種硬幣的數量是無限的。

示例?1：

輸入：coins = [1, 2, 5], amount = 11
輸出：3 
解釋：11 = 5 + 5 + 1

1. 遞歸；
2. 動態規劃；

有硬幣：【q,w,e】

思想：?

比如7個硬幣怎么使用最少的硬幣進行組合呢？

f(7) = min(f(7-q),f(7-w),f(7-e)) + 1

還有個特殊條件：?f(7-q),f(7-w),f(7-e) 存在組合（基石，不然無法站住腳）；

我這個思路不是特征的好。

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:if amount==0:return 0 coins = sorted(coins)dp = [0] * (amount+1)for i in range(amount+1):for coin in coins:if i-coin==0:dp[i] = 1elif i-coin>0:if dp[i]==0:# if dp[i-coin]==0:dp[i]==0else:dp[i] = dp[i-coin] + 1 #min(, dp[i])else:if dp[i-coin]==0:dp[i]==0else:dp[i] = min(dp[i-coin] + 1, dp[i])else:breakprint(dp)return -1 if dp[amount]==0 else dp[amount]# def sub_x(amount):#     if amount==0:#         return 0#     if amount < 0 or amount<coins[0]:#         return -1#     temp = -1#     for coin in coins:#         x = sub_x(amount - coin) # -1, >=0#         if x == -1:#             continue#         if temp==-1:#             temp = x+1#         else:#             temp = min(x+1, temp)#     return tempreturn sub_x(amount)

思路二?：陳奕迅的背包

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:n = len(coins)dp = [[amount+1] * (amount+1) for _ in range(n+1)]    # 初始化為一個較大的值，如 +inf 或 amount+1# 合法的初始化dp[0][0] = 0    # 其他 dp[0][j]均不合法# 完全背包：套用0-1背包【遍歷硬幣數目k】for i in range(1, n+1):                     # 第一層循環：遍歷硬幣for j in range(amount+1):               # 第二層循環：遍歷背包for k in range(j//coins[i-1]+1):    # 第三層循環：當前硬幣coin取k個 (k*coin<=amount)dp[i][j] = min( dp[i][j], dp[i-1][j-k*coins[i-1]] + k )ans = dp[n][amount] return ans if ans != amount+1 else -1

?思想：

1. dp[i][j]: 使用i個硬幣拼成J元最小個數;
2. 如何判斷是否放入第i+1 個硬幣呢？ 當前的容量不足以滿足硬幣金額，那么最好的揭發就是dp[i-1][j], 最好的解決策略在之前。?當前的容量>金額: 有操作的空間， min（放入+1，不放入）

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:# 11 [1,2,5]coin_len = len(coins)dp = [[amount+1]*(amount+1) for _ in range(coin_len+1)]#coins = sorted(coins)# 多大空間dp[0][0] = 0for i in range(1,coin_len+1):for j in range(amount+1):coin = coins[i-1]if j < coin:dp[i][j] = dp[i-1][j]else:dp[i][j] = min(dp[i-1][j], dp[i][j-coin]+1)# for j in range(1, coin_len+1):#     coin = coins[j-1]#     for i in range(amount+1):#         # 當前能夠到達的最大距離#         for x in range(i//coin+1):#             dp[j][i] = min(dp[j][i], dp[j-1][i-coin*x]+x)#print(dp)return -1 if dp[coin_len][amount]==(amount+1) else dp[coin_len][amount]