斐波那契数
509. 斐波那契数 – 力扣（LeetCode）
以本题为背景提出记忆化搜索
这道题的解法很多种
一：递推
二：递归
三：dp
四：记忆化搜索
五：矩阵快速幂
当然最优解是矩阵快速幂，但这里主要讲解记忆化搜索
相信经过前面的练习，不难写出递归解法
class Solution {
public:
int fib(int n) {
if(n==0||n==1){
return n;
}
return fib(n-1)+fib(n-2);
}
};
递归展开图很明显时间复杂度O(2^n)，因为有些路径重复计算了，比如这里的d(3)，两边的计算结果是一样的
记忆化搜索：
所谓的记忆化搜索，相当于弄一个备忘录，比如这里我们把d(3)加入备忘录，等右边递归进去的时候，先去看备忘录当中有没有d(3)，有直接取即可，不用往下递归
这样看能够减少绝大部分的分支，时间复杂度变成线性，直接变成O(n)
记忆化搜索：可以看成带备忘录的递归，或者可以看成剪枝版递归
如何设计一个备忘录，本质就是寻求<可变参数，返回值>
斐波那契数的可变参数是n，也就是d1，d2，d3
备忘录中存关系<int,int> <n,返回值> <可变参数，返回值>
这里可以采用数组/哈希表，因为数组的下标就可以代表n
并且备忘录要记得初始化，因为如果不初始化，递归前需要看备忘录里是否有没有，要区分备忘录是否已被设置过，比如你全设为-1，这样递归前如果发现值为-1，那就进入递归
class Solution {
public:
int memo[31];
int fib(int n) {
memset(memo, -1, sizeof(memo));
return dfs(n);
}
int dfs(int n) {
// 进入递归之前检查一下备忘录当中是否有
// 相当于剪枝
if (memo[n] != -1) {
return memo[n];
}
if (n == 0 || n == 1) {
// 递归结束之前更新备忘录
memo[n] = n;
return n;
}
// 递归结束之前更新备忘录
memo[n] = dfs(n – 1) + fib(n – 2);
return memo[n];
}
};
回顾动态规划和记忆化搜索
当你学过动态规划会发现，记忆化搜索就是一个递归形式的动态规划，之前学的动态规划是基于循环的形式，因为他们本质都是暴力搜索，本质就是把搜索过的值存起来
对于动态规划的解法
有两条路线：
1：先想爆搜，再改为动态规划，因为动态规划和记忆化搜索的本质就是一个是递推一个是递归，注意你改为记忆化搜索就不要改为动态规划了，两者的时间复杂度都一样
2：上来就是动态规划
但是如果动态规划想不出来，我们应该去想爆搜，因为爆搜能提供方向，动态规划最重要的不是状态转移方程，而是状态的定义，状态的定义就类似于dfs函数头的含义，比如斐波那契数中的dfs，dfs的含义就是给一个n我就给你返回第几个斐波那契数，那dp状态的定义就是dp[i]：i表示第i个斐波那契数
所以更好的解题思路应该是用我们的之前学的递归的思路，去给动态规划的状态下定义，提供思路，而不是盲目的想，因为爆搜基本是最简单最能想到的算法
不同路径
62. 不同路径 – 力扣（LeetCode）
这道题也是dp的经典题型
爆搜解法：这就是我们之前遇到过的
class Solution {
public:
int m;
int n;
int ret;
int dx[2]={0,1};
int dy[2]={1,0};
int uniquePaths(int _m, int _n) {
m=_m;
n=_n;
dfs(1,1);
return ret;
}
void dfs(int i,int j){
if(i==m&&j==n){
ret++;
return ;
}
for(int k=0;k<2;k++){
int x=dx[k]+i;
int y=dy[k]+j;
if(x>=1&&x<=m&&y>=1&&y<=n){
dfs(x,y);
}
}
}
};
另一种爆搜，逆着想：
但是这个会超时，因为递归的过程当中有太多的分支了
记忆化搜索：
设计备忘录
每次递归前看一下备忘录
返回前添加到备忘录
动态规划：
本质就是照搬记忆化搜索，一开始就从最底端填写dp表
而记忆化搜索是从上往下递归下去，然后再从底部填写备忘录
所以dp的状态定义和dfs函数头的含义一样，dp的状态转移方程和dfs函数体中的计算一样
最长递增子序列
300. 最长递增子序列 – 力扣（LeetCode）
按照之前的解法，就是暴力枚举，但是这个会超时
由于这里会重复计算，为什么这里可以用记忆化搜索？
因为你再算当前位置是否可以是最长递增子序列的时候，仅仅需要看比你大的那个元素的最长即可，比如你是以2起点，那你就是去看5的最长递增子序列，所以就是5的最长递增子序列+1就是2的
所以有很多地方我们重复计算
class Solution {
public:
int memo[2500];
int lengthOfLIS(vector<int>& nums) {
int ret = 0;
for (int i = 0; i < nums.size(); i++) {
ret = max(ret, dfs(nums, i));
}
return ret;
}
int dfs(vector<int>& nums, int pos) {
if(memo[pos]){
return memo[pos];
}
int count=1;
for (int i = pos + 1; i < nums.size(); i++) {
if(nums[i]>nums[pos]){
count=max(count,dfs(nums,i)+1);
}
}
memo[pos] = count;
return count;
}
};
动态规划：因为当前位置需要依赖后面的位置，所以填表顺序从后往前
猜数字大小
375. 猜数字大小 II – 力扣（LeetCode）
子问题：给一个区间，返回这个区间所需要的至少的钱，所有选择的数当中选出min，也就是区间[1,10]，给我返回一个必胜的最少的钱
但是注意我们递归左右子树回到本层的时候，左子树返回一个最少，右子树返回一个最少，我们应该再这里挑出x和y中最大+i，然后在返回，因为题目要的是必须获胜的办法，所以得挑大的
返回的min是站在全部的数字的最小，比如[1,10]，1当根节点至少要准备多少，2当根结点至少要准备多少，我要在1和2之间挑一个小的必胜的
返回的max是站在局部，因为要向上返回这次至少要准备多少，比如1要向上返回这次至少要准备多少
由于每次枚举的时候都是从一个区间开始，导致很多重复的区间
所以我们需要把计算过的区间记忆
class Solution {
public:
int memo[201][201];
int getMoneyAmount(int n) {
memset(memo,-1,sizeof(memo));
return dfs(1,n);
}
int dfs(int m, int n) {
//依次计算区间m到n中选一个最小的返回出去
if(memo[m][n]!=-1){
return memo[m][n];
}
if(m>=n){
return 0;
}
int ret=INT_MAX;
for(int i=m;i<=n;i++){
int path=max(dfs(m,i-1),dfs(i+1,n));
ret=min(path+i,ret);
}
memo[m][n]=ret;
return ret;
}
};
矩阵中的最长递增路径
329. 矩阵中的最长递增路径 – 力扣（LeetCode）
暴力解法太好想了，但是时间复杂度非常高，会超时
能否记忆化搜索？？？
也就是会不会有很多的分支可以剪掉？？？
可以，比如示例中的最长是1->2->4->9，我算2起点的时候最长是3，如果算1为起点，那就直接1+3=4即可，这样不用进入2的再算了
class Solution {
public:
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int m,n;
int memo[201][201];
int longestIncreasingPath(vector<vector<int>>& matrix) {
m=matrix.size();
n=matrix[0].size();
int ret=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
ret=max(ret,dfs(matrix,i,j));
}
}
return ret;
}
int dfs(vector<vector<int>>&matrix,int i,int j){
if(memo[i][j]){
return memo[i][j];
}
int ret=1;//细节，如果四个方向都不行的话就是为1
for(int k=0;k<4;k++){
int x=dx[k]+i;
int y=dy[k]+j;
if(x>=0&&x<m&&y>=0&&y<n&&matrix[x][y]>matrix[i][j]){
ret=max(ret,dfs(matrix,x,y)+1);//+1是因为当前位置需要+1个
}
}
memo[i][j]=ret;//返回之前存到备忘录里
return ret;
}
};
为什么需要一个返回值，也可以不用，不用的话就是你记忆化搜索之后再遍历一遍你的memo，如果有返回值，边更新边返回即可
总结
本章重点讲解了记忆化搜索，能够将原本时间复杂度非常高的爆搜降到O(n)，所谓的记忆化搜索本质就是一个带备忘录的爆搜，可以剪枝，所以时间复杂度很低
记忆化搜索又是一个递归版本的动态规划，而普通的动态规划是一个递归版本
我们可以利用爆搜的思路去给动态规划的状态下定义
