动态规划
知识点
- 动态规划与暴力解的区别
- 动态规划的四个常规步骤
- 动态规划状态转移方程的常见形式
- Top Bottom & Botton Up 的实现区别
- 了解状态压缩动态规划
- 了解计算动态规划时间复杂度的技巧
- 背包问题
有无后效性：如果对于某个状态，我们可以只关注状态的值，而不需要关注状态是如何转移过来的话，那么这就是一个无后效性的问题，可以考虑使用 DP 解决。
解题思路 ：BFS -> 记忆化搜索 -> 动态规划 思考路线：
- 如果使用暴力方法怎么做；
- 暴力方式里有哪些重复计算的部分；
- 将重复计算的部分抽成记忆化搜索；
- 存储重复计算的部分需要用到哪些参数；
- 这些参数是否就是 dp 数组的索引值；
- 使用 dp 解题
- 能否套用到背包问题（成本，价值）
- 创建几维的 dp 数组
- 如果降维需要考虑遍历顺序（通常是成本这层循环需要改为逆序）
题目
-
877. 石子游戏 20220724
-
解答 20220724
-
解答 20220720
-
494. 目标和 20220720
-
解答 20220720
-
474. 一和零 20220720
-
解答 202220720
-
1155. 掷骰子的N种方法 20220719
-
解答 20220719
-
131. 分割回文串 20220719
-
解答 20220718
-
解答 20220718
-
45. 跳跃游戏 II 20220718
-
解答 20220718
-
518. 零钱兑换 II 20220718
-
解答 20220718
-
322. 零钱兑换 20220717
-
解答 20220717
-
279. 完全平方数 20220717
-
解答 20220717
-
416. 分割等和子集 20220717
-
解答 20220717
-
1301. 最大得分的路径数目 20220717
-
解答 20220717
-
576. 出界的路径数 20220717
-
解答 20220717
-
1575. 统计所有可行路径 20220719
-
解答 20220717
-
1289. 下降路径最小和 II 20220717
-
解答 20220717
-
931. 下降路径最小和 20220715
-
解答 20220715
-
120. 三角形最小路径和 20220715
-
解答 20220715
-
64. 最小路径和 20220715
-
解答 20220715
-
63. 不同路径 II 20220715
-
解答 20220715
-
62. 不同路径 20220715
-
解答 20220715