1D Dynamic Programming

一維動態規劃用決策樹分析。

• 70. Climbing Stairs
  一次爬1或2階，種方式到終點
  
  相同數字有相同Decision Tree
  
  Bottom-up陣列表示
  

  • 213. House Robber II
    70基礎上第一個跟最後相接

• 322. Coin Change
  選取，扣除，有相同子問題
  
  Bottom-up陣列表示
  

  • 518. Coin Change II Two dimension

• 139. Word Break
  從候選字index開始看
  
  符合字填True
  

• 300. Longest Increasing Subsequence
  一個個取
  
  將最長紀錄存到陣列，但是nˆ2，可以用耐心排序nlogn
  

• 98. House Robber
  決策樹選取
  

• 416. Partition Equal Subset Sum
  是否取每個值
  

• 91. Decode Ways
  

• 97.Interleaving String
  s1 = “aabcc”, s2 = “dbbca” 穿插可否變 s3 = “aadbbcbcac”
  (0,0)紀錄(s1, s2)字串位置
  

• 494. Target Sum
  (index, total)
  

class Solution:    
    def findTargetSumWays(self, nums: List[int], target: int) -> int:     
        n = len(nums)
        dp = {}
        def dfs(i,target):
            if (i,target) in dp:
                return dp[(i,target)]
            if i >= n:
                if target == 0:
                    return 1
                else:
                    return 0
            dp[(i,target)] = dfs(i+1,target - nums[i]) + dfs(i+1,target + nums[i]) 
            return dp[(i,target)]
        return dfs(0,target)

• 309. Best Time to Buy and Sell Stock with Cooldown
• 5. Longest Palindromic Substring
• 152. Maximum Product Subarray

Image Credits: Neetcode

---

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