链接
题目：
方法一：递归+备忘录（重叠子问题）
动态规划问题一般形式就是求最值；
因为要求最值，所以动态规划的核心问题是穷举；
- 需要掌握递归思维，只有列出正确的「状态转移方程」，才能正确地穷举；
- 而且需要判断算法问题是否具备「最优子结构」，是否能够通过?问题的最值得到原问题的最值；
- 另外，动态规划问题存在「重叠子问题」，如果暴?穷举的话效率会很低，所以需要使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
状态转移方程、最优子结构、重叠子问题 就是动态规划三要素 ；
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
如果代码为：
class Solution {
public int fib(int n) {
//终止条件
if(n==0 || n==1){
return n;
}
return fib(n-1)+fib(n-2);
}
}
则会有重复计算------------重叠子问题
假设n=20：
20以下的每个节点都被计算了两次 ！
每个节点的时间复杂度为O(1) ，而节点数为O(2^n)，所以时间复杂度为O(1) x O(2^n) =O(2^n)，效率低；
dp定义：输入n，返回n的斐波那契数之和；
dp函数的参数n就是状态；
使用备忘录数组来解决重叠子问题：
返回值 (回溯) 就是要计算的值！**
class Solution {
int[] memo;
public int fib(int n) {
memo=new int[n+1];
Arrays.fill(memo,-111);//初始化memo以免弄混
return dp(n);
}
int dp(int n){ // dp参数n 是状态
// base case
if(n==1 || n==0){
return n;
}
// 重叠子问题
if(memo[n]!=-111){
return memo[n];
}
// 状态转移方程 回溯
memo[n]=dp(n-1)+dp(n-2);
return memo[n]; // dp返回值为所求的和
}
}
或者用HashMap来作为备忘录，n为Key，n的计算结果为Value：
class Solution {
HashMap<Integer,Integer> memo=new HashMap<>();
public int fib(int n) {
return check(n);
}
int check(int n){
if(n==0 || n==1){
return n;
}
if(memo.containsKey(n)){ // 已计算过, 避免重叠子问题
return memo.get(n);
}
memo.put( n, check(n-1)+check(n-2) );
return memo.get(n);
}
}
带「备忘录」的递归算法，把?棵存在巨量冗余的递归树通过「剪枝」，改造成了?幅不存在冗余 的递归图，极?减少了?问题（即递归图中节点）的个数；
以上解法是「自顶向下」进?「递归」求解，我们更常?的动态规划代码是「自底向上」进?「递推」求解。
啥叫「自顶向下」？注意我们刚才画的递归树（或者说图），是从上向下延伸，都是从?个规模较?的原问 题?如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 这两个 base case，然后逐层返回答案，这就叫 「?顶向下」。
啥叫「自底向上」？反过来，直接从最底下、最简单、问题规模最?、已知结果的 f(1) 和 f(2)（base case）开始往上推，直到推到想要的答案 f(20)。这就是「递推」的思路，这也是动态规划?般都脱离了递归，?是由循环迭代完成计算的原因。
方法二：递推迭代 + DP Table
引出「状态转移方程」这个名词，实际上就是描述问题结构的数学形式：
f(n) 的函数参数会不断变化，所以你把参数 n 想做?个状态，这个状态 n 是由状态 n - 1 和状态 n - 2转移（相加）?来，这就叫状态转移
动态规划问题最困难的就是写出这个状态转移方程；
只要写出暴力解，优化方法无非是用备忘录或者 DP table
利用DP table数组 自底向上递推：
class Solution {
public int fib(int n) {
if(n==0){
return 0;
}
int[] dp=new int[n+1];
//base case
dp[0]=0;
dp[1]=1;
// 自底向上递推
for(int i=2;i<=n;i++){ // 遍历共2-n种状态
dp[i]=dp[i-1]+dp[i-2]; // 状态转移
}
return dp[n];
}
}