動態規劃練習題 (DP)

# 動態規劃 (DP) ## 一維 DP | 題號 | 題目名稱| 難度 | 備註 | 題解 | | ---- | ------------------------------------------------------------------------ | -------------------------------- |:------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------:| ----------------------------------------------------------- | |509|[Fibonacci Number](https://leetcode.com/problems/fibonacci-number/)|Easy||[Fibonacci Number 題解](https://hackmd.io/@paxton0222/H18CNY01T)| |1646|[Get Maximum in Generated Array](https://leetcode.com/problems/get-maximum-in-generated-array/)|Easy||[Get Maximum in Generated Array 題解](https://hackmd.io/@paxton0222/rkxOGXmFxa)| |338|[Counting Bits](https://leetcode.com/problems/counting-bits/description/)|Easy| Bit Manipulations + DP |[Counting Bits 題解](https://hackmd.io/@paxton0222/Sk1siiDgp)| |1137|[N-th Tribonacci Number](https://leetcode.com/problems/n-th-tribonacci-number/)|Easy||[N-th Tribonacci Number 題解](https://hackmd.io/@paxton0222/B1PuNrbga)| |121|[Climbing Stairs 爬樓梯](https://leetcode.com/problems/climbing-stairs/)|Easy||[Climbing Stairs 題解](https://hackmd.io/@paxton0222/BkCw92ty6)| |198|[House Robber](https://leetcode.com/problems/house-robber/?envType=study-plan-v2&envId=top-interview-150)|Medium||[House Robber 題解](https://hackmd.io/@paxton0222/rk8LAgllp)| |1641|[Count Sorted Vowel Strings](https://leetcode.com/problems/count-sorted-vowel-strings/)|Medium|前綴和 + DP|[Count Sorted Vowel Strings 題解](https://hackmd.io/@paxton0222/rJOfirFlT)| |300|[Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/description/)|Medium|Greedy + Binary Search、DP|[Longest Increasing Subsequence 題解](https://hackmd.io/@paxton0222/HJxvdGLo2)| |139|[Word Break](https://leetcode.com/problems/word-break/)|Medium|Trie、Memory Trie、DP|[Word Break 題解](https://hackmd.io/@paxton0222/BJfTcCwe6)| |343|[Integer Break](https://leetcode.com/problems/integer-break/)|Medium||[Integer Break 題解](https://hackmd.io/@paxton0222/Sk7zjc6ga)| |322|[Coin Change](https://leetcode.com/problems/coin-change/)|Medium|無限背包問題 (Bottom up 尚未達到最優)|[Coin Change 題解](https://hackmd.io/@paxton0222/HkAQ2Nrxp) ## 多維 DP | 題號 | 題目名稱| 難度 | 備註 | 題解 | | ---- | ------------------------------------------------------------------------ | -------------------------------- |:------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------:| ----------------------------------------------------------- | |118|[Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/)|Easy||[Pascal's Triangle 題解](https://hackmd.io/@paxton0222/rkYyBbdxp)| |119|[Pascal's Triangle II](https://leetcode.com/problems/pascals-triangle-ii/)|Easy||[Pascal's Triangle II 題解](https://hackmd.io/@paxton0222/rJ75XEdgT)| |120|[Triangle](https://leetcode.com/problems/triangle/)|Medium||[Triangle 題解](https://hackmd.io/@paxton0222/BJ7YkSlla)| |62|[Unique Paths](https://leetcode.com/problems/unique-paths/description/)|Medium||[Unique Paths 題解](https://hackmd.io/@paxton0222/ByAn7pJep)| |63|[Unique Paths II](https://leetcode.com/problems/unique-paths-ii/description/)|Medium||[Unique Paths II 題解](https://hackmd.io/@paxton0222/rkbSfzll6)| |64|[Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/)|Medium||[Minimum Path Sum 題解](https://hackmd.io/@paxton0222/B1Q97Zggp)| |221|[Maximal Square](https://leetcode.com/problems/maximal-square/)|Medium||[Maximal Square 題解](https://hackmd.io/@paxton0222/SJzt8y7ga) |1277|[Count Square Submatrices with All Ones](https://leetcode.com/problems/count-square-submatrices-with-all-ones/)|Medium||[Count Square Submatrices with All Ones 題解](https://hackmd.io/@paxton0222/HJU0M3Qea) |894|[All Possible Full Binary Trees](https://leetcode.com/problems/all-possible-full-binary-trees/)|Medium||[All Possible Full Binary Trees 題解](https://hackmd.io/@paxton0222/SyRSpVYe6) |5|[Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)|Medium| Brute force、DP (matrix)、DP (O(1))、Manacher’s algorithm |[Longest Palindromic Substring 題解](https://hackmd.io/@paxton0222/HJ_g_oclp) |97|[Interleaving String](https://leetcode.com/problems/interleaving-string/)|Medium||[Interleaving String 題解](https://hackmd.io/@paxton0222/BJSfk-Tgp)