---
# System prepended metadata

title: 動態規劃練習題 (DP)

---

# 動態規劃 (DP)

## 一維 DP

| 題號 | 題目名稱| 難度 | 備註 | 題解 |
| ---- | ------------------------------------------------------------------------ | -------------------------------- |:------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------:| ----------------------------------------------------------- |
|509|[Fibonacci Number](https://leetcode.com/problems/fibonacci-number/)|<font color=DarkGreen>Easy</font>||[Fibonacci Number 題解](https://hackmd.io/@paxton0222/H18CNY01T)|
|1646|[Get Maximum in Generated Array](https://leetcode.com/problems/get-maximum-in-generated-array/)|<font color=DarkGreen>Easy</font>||[Get Maximum in Generated Array 題解](https://hackmd.io/@paxton0222/rkxOGXmFxa)|
|338|[Counting Bits](https://leetcode.com/problems/counting-bits/description/)|<font color=DarkGreen>Easy</font>| Bit Manipulations + DP |[Counting Bits 題解](https://hackmd.io/@paxton0222/Sk1siiDgp)|
|1137|[N-th Tribonacci Number](https://leetcode.com/problems/n-th-tribonacci-number/)|<font color=DarkGreen>Easy</font>||[N-th Tribonacci Number 題解](https://hackmd.io/@paxton0222/B1PuNrbga)|
|121|[Climbing Stairs 爬樓梯](https://leetcode.com/problems/climbing-stairs/)|<font color=DarkGreen>Easy</font>||[Climbing Stairs 題解](https://hackmd.io/@paxton0222/BkCw92ty6)|
|198|[House Robber](https://leetcode.com/problems/house-robber/?envType=study-plan-v2&envId=top-interview-150)|<font color=Orange>Medium</font>||[House Robber 題解](https://hackmd.io/@paxton0222/rk8LAgllp)|
|1641|[Count Sorted Vowel Strings](https://leetcode.com/problems/count-sorted-vowel-strings/)|<font color=Orange>Medium</font>|前綴和 + DP|[Count Sorted Vowel Strings 題解](https://hackmd.io/@paxton0222/rJOfirFlT)|
|300|[Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/description/)|<font color=Orange>Medium</font>|Greedy + Binary Search、DP|[Longest Increasing Subsequence 題解](https://hackmd.io/@paxton0222/HJxvdGLo2)|
|139|[Word Break](https://leetcode.com/problems/word-break/)|<font color=Orange>Medium</font>|Trie、Memory Trie、DP|[Word Break 題解](https://hackmd.io/@paxton0222/BJfTcCwe6)|
|343|[Integer Break](https://leetcode.com/problems/integer-break/)|<font color=Orange>Medium</font>||[Integer Break 題解](https://hackmd.io/@paxton0222/Sk7zjc6ga)|
|322|[Coin Change](https://leetcode.com/problems/coin-change/)|<font color=Orange>Medium</font>|無限背包問題 (Bottom up 尚未達到最優)|[Coin Change 題解](https://hackmd.io/@paxton0222/HkAQ2Nrxp)

## 多維 DP

| 題號 | 題目名稱| 難度 | 備註 | 題解 |
| ---- | ------------------------------------------------------------------------ | -------------------------------- |:------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------:| ----------------------------------------------------------- |
|118|[Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/)|<font color=DarkGreen>Easy</font>||[Pascal's Triangle 題解](https://hackmd.io/@paxton0222/rkYyBbdxp)|
|119|[Pascal's Triangle II](https://leetcode.com/problems/pascals-triangle-ii/)|<font color=DarkGreen>Easy</font>||[Pascal's Triangle II 題解](https://hackmd.io/@paxton0222/rJ75XEdgT)|
|120|[Triangle](https://leetcode.com/problems/triangle/)|<font color=Orange>Medium</font>||[Triangle 題解](https://hackmd.io/@paxton0222/BJ7YkSlla)|
|62|[Unique Paths](https://leetcode.com/problems/unique-paths/description/)|<font color=Orange>Medium</font>||[Unique Paths 題解](https://hackmd.io/@paxton0222/ByAn7pJep)|
|63|[Unique Paths II](https://leetcode.com/problems/unique-paths-ii/description/)|<font color=Orange>Medium</font>||[Unique Paths II 題解](https://hackmd.io/@paxton0222/rkbSfzll6)|
|64|[Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/)|<font color=Orange>Medium</font>||[Minimum Path Sum 題解](https://hackmd.io/@paxton0222/B1Q97Zggp)|
|221|[Maximal Square](https://leetcode.com/problems/maximal-square/)|<font color=Orange>Medium</font>||[Maximal Square 題解](https://hackmd.io/@paxton0222/SJzt8y7ga)
|1277|[Count Square Submatrices with All Ones](https://leetcode.com/problems/count-square-submatrices-with-all-ones/)|<font color=Orange>Medium</font>||[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/)|<font color=Orange>Medium</font>||[All Possible Full Binary Trees 題解](https://hackmd.io/@paxton0222/SyRSpVYe6)
|5|[Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)|<font color=Orange>Medium</font>| 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/)|<font color=Orange>Medium</font>||[Interleaving String 題解](https://hackmd.io/@paxton0222/BJSfk-Tgp)
