0/1 Knapsack

或許人生就是多道是非題。

相同選取的題型就是0/1背包問題。

背景知識

• 基礎程式語法
• 背包問題

理解問題

從地圖左上到右下，一次只能選一個方向，有幾種走法。

每相同選擇問題就是動態規劃拿手的。

思路視覺化

Input: m = 3, n = 2
Output: 3

60
00
09

3*2地圖，6的位置要移到9，有 r: right, d: down
rdd
ddr
drd
三種走法

程式化

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp=[[1]*n for _ in range(m)] # [[1]*n]*m
        
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j]+dp[i][j-1] # 轉移矩陣
        return dp[-1][-1]

更精簡做法

複雜度分析

由於走訪地圖，時間空間複查度都是O (mn)

問題

1. Unbound Knapsack

---

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