动态规划 的总结

2021-02-03  本文已影响0人  小星star

一 、动态规划做题套路总结:

  常见的转移方程
  dp[i] = dp[i - 1] , dp[i - 2]
  dp[i] = dp[i - j] , !dp[i - j]
  etc

二、做过的题目总结

建议按顺序尝试

简单动态规划
53 最大子序和
746 使用最小花费爬楼梯
1025 除数博弈
70 爬楼梯

中等动态规划
650 只有两个键的键盘
剑指offer63 股票的最大利润
198 打家劫舍
221 最大正方形
931 下降路径最小和
14 14- I. 剪绳子
62 不同路径

高难动态规划
32 最长有效括号

三、动态规划优化:

  1. 从前往后,避免递归
  2. 空间优化,滚动数组 或者 常数级变量

四、目前还不太会的动态规划

  1. 多维的动态规划,一看就很烦

    例题 有哪些

  2. 有的不明所以,不知道 dp[][] 应该代表什么

    例题有

  3. 有的不会写状态方程

    例题有

五、对于 动态规划 的一些有利于理解的文章

上一篇 下一篇

猜你喜欢

热点阅读