概念
举例
拿斐波那契数列举例
可以发现一般的求解过程中,有很多重复的子问题,递归的本质就是深度优先遍历,如果此时我们可以记录下此时的值然后记录在哈希表中,下一次递归前先去哈希表中查找如果有该值的答案直接返回即可。
这样完全二叉树就可以转为单链结构
应用
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_maphash; 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;ifor(int j=i+1;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> & 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 >& matrix) { memset(dp,-1,sizeof dp); int m=matrix.size(); int n=matrix[0].size(); int len=1; for(int i=0;i for(int j=0;j len=max(len,dfs(matrix,m,n,i,j)); } } return len; } };
思路:总体思路是对每一个点进行一次dfs,同时用记忆化搜索优化代码(否则会超时)