【二叉树】【动态规划】1、斐波那契数+2、零钱兑换

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++){//循环所有状态2for(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];}
};