从递归/记忆化搜索入手动态规划
在入门动态规划时，记忆化搜索往往比递推形式更容易想。可以先写出记忆化搜索，再转为递推形式。
记忆化搜索很好用，但并不是万能的，某些题目只有写成递推，才能结合数据结构等来优化时间复杂度，多数题目还可以优化空间复杂度。
力扣 509. 斐波那契数
洛谷 P1048 「NOIP 2005 普及组」 采药
下面以斐波那契为例：
暴力搜索
很容易实现这样一个朴素的搜索做法：
publicstaticintf1(inti){if(i==0){return0;}if(i==1){return1;}returnf1(i-1)+f1(i-2);}时间复杂度：O ( 2 n ) O(2^n)O(2n)。搜索树可以近似为一棵二叉树，树高为 n，节点个数为O ( 2 n ) O(2^n)O(2n)。
空间复杂度：O ( n ) O(n)O(n)。递归需要O ( n ) O(n)O(n)的栈空间。
这种做法的时间复杂度是指数级别的，不是我们希望的。
记忆化搜索
上面的做法为什么效率低下呢？因为同一个状态会被访问多次。
记忆化搜索是一种通过记录已经遍历过的状态的信息，从而避免对同一状态重复遍历的搜索实现方式。
这充分利用了动态规划中很多问题具有大量重叠子问题的特点，属于用空间换时间的「记忆化」思想。
// memo 为记忆化数组，初始化为 -1publicstaticintf2(inti,int[]memo){if(i==0){return0;}if(i==1){return1;}if(memo[i]!=-1){returnmemo[i];}intans=f2(i-1,memo)+f2(i-2,memo);memo[i]=ans;returnans;}时间复杂度：O ( n ) O(n)O(n)。动态规划的时间复杂度 = 状态个数 × 单个状态的计算时间，且每个状态只会计算一次。
- 或者可以这样理解：记忆化搜索的递归树可以想象为一颗左斜树，但每个节点都有一个长度为 1 的右子树（用了记忆化，所以是不展开的小毛刺），于是时间复杂度 =O ( 2 n ) O(2n)O(2n)=O ( n ) O(n)O(n)。
空间复杂度：O ( n ) O(n)O(n)。memo数组。
递推
在求解动态规划的问题时，记忆化搜索与递推的代码，在形式上是高度类似的。这是由于它们使用了相同的状态表示方式和类似的状态转移。一般来说两种实现的时间复杂度是一样的。
publicstaticintfib3(intn){if(n==0){return0;}if(n==1){return1;}int[]f=newint[n+1];f[1]=1;for(inti=2;i<=n;i++){f[i]=f[i-1]+f[i-2];}returnf[n];}时间复杂度：O ( n ) O(n)O(n)。
空间复杂度：O ( n ) O(n)O(n)。
在求解动态规划的问题时，记忆化搜索和递推，都确保了同一状态至多只被求解一次。但实现的策略有所不同：递推通过设置明确的访问顺序来避免重复访问，记忆化搜索通过给已经访问过的状态打标记的方式，也达到了同样的目的。
与递推相比，记忆化搜索因为不用明确规定访问顺序，在实现难度上有时低于递推，且能比较方便地处理边界情况，这是记忆化搜索的一大优势。但与此同时，记忆化搜索难以使用滚动数组，数据结构等优化，且由于存在递归，运行效率会低于递推。
优化
观察状态转移方程，发现一旦算出 f[i]，那么 f[i−2] 及其左边的状态就永远不会用到了，于是我们可以用几个变量，把空间复杂度优化成O ( 1 ) O(1)O(1)。
publicintfib(intn){if(n==0){return0;}if(n==1){return1;}intf0=0,f1=1;for(inti=2;i<=n;i++){intnewF=f0+f1;f0=f1;f1=newF;}returnf1;}以下是我认为最有代表性的一些题。
爬楼梯
通常可以用「枚举选哪个」的搜索思想。
力扣 70. 爬楼梯
力扣 2266. 统计打字方案数 每次可以爬 3 或 4 层
打家劫舍
通常可以用「选或不选」的搜索思想。
力扣198. 打家劫舍 从最左或最右切入可以简化问题
力扣 740. 删除并获得点数 值域打家劫舍
力扣 3186. 施咒的最大总伤害 数据规模更大的 值域打家劫舍
力扣 2140. 解决智力问题 刷表法：用现在的状态更新未来的状态。与之对比的是查表法：用之前的状态计算当前的状态
