1、遍历：在遍历的过程中就能够解决问题，只需要递归函数的参数即可。
2、子树：只有在遍历完成之后才能解决问题，还需要递归函数的返回值。（需要在后序位置写代码）
动态规划：子树 核心思想是穷举求最值
动态规划三要素：
正确的状态转移方程
具有最优子结构
存在重叠子问题（暴力穷举效率很低，需要使用备忘录（dp table)来优化穷举过程）
明确状态，明确选择，定义dp数组
回溯算法：树枝
DFS算法：节点
1、斐波那契数（难度：简单）
AC方法和对应代码
1、暴力递归穷举
重复计算太多
时间复杂度是O(2的n次方)
class Solution {
public:
//暴力递归穷举
int fib(int n) {
if(n==0 || n==1){
return n;
}
return fib(n-1)+fib(n-2);
}
};
2、带备忘录的递归解法
使用备忘录数组或者字典（这里用的数组）来记录每次已经算过的fib(n)，避免重复计算
时间复杂度是O(n)
class Solution {
public:
//带备忘录的递归解法
int fib(int n) {
int nums[n+1];
memset(nums,-1,sizeof(nums));
return dp(nums, n);
}
int dp(int nums[], int n){
if(n==0 || n==1){
nums[n]=n;
}
//备忘录
if(nums[n]!=-1){
return nums[n];
}
return dp(nums,n-1)+dp(nums,n-2);
}
};
3、dp数组的迭代(递推)解法(for循环)
前面两种方法都是自顶向下，然后最后通过返回值将答案返回给上级，本质上是自顶向下的思路。
这种方法是自底向上，仍然使用备忘录（数组）来辅助完成推算。
（注意：声明一个n+2的数组int dp[n+2]，因为dp[0]=0,dp[1]=1，当n<2的时候，不这么定义会出现数组下标溢出的情况。）
class Solution {
public:
int fib(int n) {
int dp[n+2];
dp[0]=0;
dp[1]=1;
for(int i=2;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
};
以上斐波那契数的题目也不算严格意义上的动态规划题目，只因为涉及到重叠子问题的消除。
暴力解的优化方法是用备忘录或者dp table
斐波那契数还有优化方法，可以将时间复杂度降为o(1)
把dp table的大小从n缩小到n
2、零钱兑换（难度：中等）
（看不懂啊看不懂，狗头保命）
该题对应力扣网址
动态规划递归模板
# 自顶向下递归的动态规划
def dp(状态1, 状态2, ...):
for 选择 in 所有可能的选择:
# 此时的状态已经因为做了选择而改变
result = 求最值(result, dp(状态1, 状态2, ...))
return result
动态规划迭代模板
# 自底向上迭代的动态规划
# 初始化 base case
dp[0][0][...] = base case
# 进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 求最值(选择1，选择2...)
超出时间限制
由于重复计算，导致超时严重。。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
return dp(coins,amount);
}
//状态是amount，即本题中的变量
//选择：能够使状态发生变化，本题中指的是不同面值的硬币及个数
//dp函数，函数参数包含状态，函数返回值是题目需要计算的值
int dp(vector<int>& coins, int amount){
if(amount==0){
return 0;
}
if(amount<0){
return -1;
}
int res=INT_MAX;
//对所有可能的选择
for(int coin: coins){
int subsum=dp(coins,amount-coin);
if(subsum==-1)continue;
res=min(res,subsum+1);
}
return res==INT_MAX?-1:res;
}
};
AC代码（递归+备忘录）
设置一个dp数组来作为备忘录
写的时候出现了两个问题：
1、备忘录数组的初始化问题，memset(memo,-1,sizeof(memo))用这个初始化方法初始化后不对~~（原理我之后再补）~~
2、一开始加上备忘录之后还是超时，后来发现备忘录数组其实和最后的res是一个值，所以应该放在返回值的地方再确定备忘录数组的值。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
//定义一个备忘录
// int memo[amount+1]={-2};
int* memo = new int[amount + 1];
for (int i = 0; i <= amount; ++i) {
memo[i] = -2;
}
// memset(memo,-1,sizeof(memo));
// cout<<"尺寸："<<sizeof(memo)<<endl;
// cout<<"初始化："<<memo[0]<<endl;
return dp(memo,coins,amount);
}
//
int dp(int memo[], vector<int>& coins, int amount){
if(amount==0){
return 0;
}
if(amount<0){
return -1;
}
if(memo[amount]!=-2){
return memo[amount];
}
int subsum;
int res=INT_MAX;
for(int coin: coins){
// if(amount-coin>=0 && memo[amount-coin]!=-2){
// res=memo[amount-coin];
// }
subsum=dp(memo,coins,amount-coin);
if(subsum==-1)continue;
res=min(res,subsum+1);
}
if(res==INT_MAX){
res=-1;
}
memo[amount]=res;
return res;
}
};
AC代码（迭代+dp数组）
看完题解了解完主要思路之后，终于把这个代码复现下来了，发现代入具体例子之后，才懂了在什么地方求最小值等等。
做的时候有个地方，就是int+int超出了数据范围报错，于是改成了相减amount-i-coin，解决了超限问题。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
//迭代+dp数组
int *dp = new int[amount+1];
//base case dp[0]
for(int j=1;j<=amount;j++){
dp[j]=-1;
}
dp[0]=0;
int res=INT_MAX;
//进行状态转移
//循环所有的状态1,原递归的参数
for(int i=0;i<=amount;i++){
//循环所有状态2
for(int coin:coins){
if(dp[i]==-1)continue;
res=dp[i]+1;
if((amount-i-coin)<0)continue;
if(dp[i+coin]!=-1){
dp[i+coin]=min(res,dp[i+coin]);
}
else{
dp[i+coin]=res;
}
//dp[1]=dp[0]+1=1
//dp[2]=dp[0]+1=1
//dp[5]=dp[0]+1=1
//dp[1+1]=dp[2]=dp[1]+1=2
//dp[1+2]=dp[3]=dp[1]+1=2
//dp[1+5]=dp[6]=dp[1]+1=2
//dp[2+1]=dp[3]=dp[2]+1=3
//dp[2+2]=dp[4]=dp[2]+1=3
//dp[2+5]=dp[7]=dp[2]+1=3
//...
//dp[6+5]=dp[6]+1=3
//例如：
//dp[2]=1=2
}
}
return dp[amount];
}
};
从二叉树过来的，听说二叉树的思路可以延伸出来动态规划和回溯等算法，动态规划看了好几天的讲解，现在还是迷糊，费老大劲根据题解写完了两道题，总算有点思路了。