Linear DP

• Ref - Linear DP1

• Ref - Linear DP2

• Top-down: Recursion

• Bottom-up: Iteration

LeetCode 53. Maximum Subarray

LeetCode 300. Longest Increasing Subsequence

LeetCode 1143. Longest Common Subsequence

LeetCode 935. Knight Dialer

LeetCode 873. Length of Longest Fibonacci Subsequence

• Ref - LIS

LeetCode 72. Edit Distance

LeetCode 221. Maximal Square

LeetCode 343. Integer Break

LeetCode 650. 2 Keys Keyboard

LeetCode 740. Delete and Earn

• 扁平化成 House Robber 問題

LeetCode 1027. Longest Arithmetic Subsequence

• 對於公差為負數的情況，可以將範圍整體平移成正數

LeetCode 718. Maximum Length of Repeated Subarray

LeetCode 368. Largest Divisible Subset

• 使用兩個 vector 來分別記錄最大長度以及轉移的 index

• Ref - 題解

LeetCode 91. Decode Ways

• Ref - 題解

LeetCode 1220. Count Vowels Permutation

LeetCode 338. Counting Bits

• 當 是奇數，必定是 ⇒ 多出來的 1 就是最後一個 bit

• 當 是偶數，必定是 ⇒ 將 右移一位變成 ，1 的個數不變