概念
举例
拿斐波那契数列举例
可以发现一般的求解过程中，有很多重复的子问题，递归的本质就是深度优先遍历，如果此时我们可以记录下此时的值然后记录在哈希表中，下一次递归前先去哈希表中查找如果有该值的答案直接返回即可。
这样完全二叉树就可以转为单链结构
应用
leetcode397.整数替换
给定一个正整数 n ，你可以做如下操作：
如果 n 是偶数，则用 n / 2替换 n 。
如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
返回 n 变为 1 所需的 最小替换次数 。
示例 1：
输入：n = 8
输出：3
解释：8 -> 4 -> 2 -> 1
示例 2：
输入：n = 7
输出：4
解释：7 -> 8 -> 4 -> 2 -> 1
或 7 -> 6 -> 3 -> 2 -> 1
class Solution {
public:
unordered_map<int,int> hash;
int integerReplacement(int n) {
if(n==1)
return 0;
int ans=0;
if(hash.count(n))
return hash[n];
if(n%2==0)
{
ans=integerReplacement(n/2)+1;
}
else
{
ans=min(integerReplacement(n/2+1)+1,integerReplacement(n-1))+1;
}
hash[n]=ans;
return ans;
}
};
leetcode647.回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”
示例 2：
输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
class Solution {
int dp[1000][1000];
int dfs(const string& s,int l,int r)
{
if(l>r)
return 1;
if(dp[l][r]!=-1)
return dp[l][r];//记忆化搜索
if(s[l]==s[r])
dp[l][r]=dfs(s,l+1,r-1);
else
dp[l][r]=0;
return dp[l][r];
}
public:
int countSubstrings(string s) {
int n=s.size();
memset(dp,-1,sizeof(dp));
int ans=0;
for(int i=0;i<n;i++)
dp[i][i]=1,ans++;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(dp[i][j]==-1)
{
dp[i][j]=dfs(s,i,j);
}
if(dp[i][j]==1)
++ans;
}
}
return ans;
}
};
思路：这里我们用ans记录回文子序列的个数，dp[i][j]表示从i位置到j位置是否为回文子序列，当i=j即单个元素是回文串，然后两层循环遍历每一个子序列，状态转移方程：dp[i][j]=s[i]==s[j] and dp[i+1][j-1],这里可以采用记忆化搜索的方式，定义一个dfs函数，记录从开头到结尾的子序列是否是回文的。
lcr112.矩阵中的最长递增路径（hard）
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
示例 1：
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4
解释：最长递增路径为 [1, 2, 6, 9]。
示例 2：
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
class Solution {
int dp[200][200];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int dfs(vector<vector<int>> & matrix,int m,int n,int i,int j)
{
if(dp[i][j]!=-1)
return dp[i][j];
int len=1;
for(int a=0;a<4;a++)
{
int x=i+dx[a],y=j+dy[a];
if(x<0||y<0||x>m-1||y>n-1)
continue;
if(matrix[x][y]<=matrix[i][j])
continue;
len=max(len,dfs(matrix,m,n,x,y)+1);
}
dp[i][j]=len;
return len;
}
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
memset(dp,-1,sizeof dp);
int m=matrix.size();
int n=matrix[0].size();
int len=1;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
len=max(len,dfs(matrix,m,n,i,j));
}
}
return len;
}
};
思路：总体思路是对每一个点进行一次dfs，同时用记忆化搜索优化代码（否则会超时）
