Algorithm: Dynamic Programming

Dynamic Programming(DP) 根本是透過把大問題分成子問題達到最優解, 那跟 Divide and Conquer 有什麼差別呢？ 什麼是轉換方程?

Divder and Conquer V.S Dynamic Programming

Divide and Conquer	Dynamic Programming
通常是用遞迴方式由根向下的解題過程	通常是透過轉換方程由小問題的最優解推至大問題的最優解
常常會有出現重複計算, 造成時間複雜度提高	會將計算過的結果存下來, 有較佳的時間複雜度

轉換方程

如何將小問題的最優解推導成大問題的最優解

l(n) = l(n-1) + l(n-2)

LeetCode 70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

第 n 階 的走法可以是從第 n-1 階走一步或從第 n-2 階走兩步, 所以當第 n-1 階有 K 種走法，第 n-2 階有 L 種走法時第 n 階有 K+ L 種

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 3:
            return n 

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

        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2] # <--- 轉換方程

        return dp[n]
         

LeetCode 322. Coin Change

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

當要換 N 元時， 使用 A, B 元硬幣換，用 A 元換需要最少需要 Ｋ 個硬幣， 用 B 元換的最小硬幣數量為 N-B 的最小硬幣數量+1 和 K 的最小值

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        dp = [amount+1 for _ in range(amount+1)]
        dp[0] = 0
        for dollars in range(1, amount+1):
            for coin in coins:
                if dollars >= coin:
                    dp[dollars] = min(dp[dollars-coin] + 1, dp[dollars]) # 轉換方程

        return dp[amount] if dp[amount] != amount+1 else -1