当前位置：首页 > news >正文

记忆化搜索——1

news 来源：原创 2024/9/22 9:30:20

1.斐波那契数

2.不同路径

3.最长递增子序列

4.猜数字大小2

5.矩阵中的最长递增路径

1.斐波那契数

该题规律很明显，就直接放记忆化搜索的版本了

class Solution {
public:int dfs(int n){if(n==0||n==1)//递归出口{return n;}if(f[n-1]==-1)//检查是否已经记忆过{f[n-1]=dfs(n-2)+dfs(n-3);}if(f[n-2]==-1)//检查是否已经记忆过{f[n-2]=dfs(n-3)+dfs(n-4);}return f[n]=f[n-1]+f[n-2];//状态转移}int fib(int n) {memset(f,-1,sizeof f);f[0]=0,f[1]=1;dfs(n);return f[n];}int f[31];};

2.不同路径

class Solution {
public:int dfs(int x, int y){if (x < 1 || y < 1)return 0;//防止越界if (x == 1 && y == 1)return f[x][y];//递归出口if (f[x][y] == -1)//检查是否记忆{f[x][y] = dfs(x - 1, y) + dfs(x, y - 1);}return f[x][y];}int uniquePaths(int m, int n) {memset(f, -1, sizeof f);f[1][1] = 1;return dfs(m, n);}long long f[101][101];
};

3.最长递增子序列

class Solution {
public:void dfs(vector<int>& nums,int index){int ret=1;//临时存放index位置为起点的最长递增子序列长度，因为一个数字最起码长度为1，所以ret默认1for(int i=index+1;i<n;i++){if(nums[index]<nums[i]){if(f[i]==0)dfs(nums,i);//检查标记，剪枝操作ret=max(ret,f[i]+1);//注意+1,因为f是以i为起点的最长递增子序列长度}}f[index]=ret;ans=max(ans,f[index]);}int lengthOfLIS(vector<int>& nums) {n=nums.size();
//以第i位为起点的最长递增子序列长度for(int i=0;i<n;i++){if(f[i]!=0)continue;dfs(nums,i);}
//ans存的是这些最长递增子序列中最长的长度return ans;
//注意，我试过当前函数直接一个dfs，然后直接返回，因为最后f所有位置都要填上，所以
//我直接在dfs里疯狂展开，没填就展开，也可以过，但是效率比在这里用for循坏差一点，几十毫秒的差距}int ans=0;int n;int f[2501];//存以当前位置为起点的最长递增子序列长度
};

4.猜数字大小2

class Solution {
public:void dfs(int l,int r){if(l>=r){return ;}
//注意，如果l>r，说明这不是一个合法区间，不用管
//如果l==r，说明没必要付钱，因为这个数字是一定会被找到的
//而f数组默认都是0，所以直接返回就好int ret=99999999;
//一个大数，因为下面要用来比小for(int i=l;i<=r;i++){if(f[l][i-1]==0)dfs(l,i-1);if(f[i+1][r]==0)dfs(i+1,r);
//检查标记，剪枝操作ret=min(ret,i+max(f[l][i-1],f[i+1][r]));
//这个部分看图,主要是，一个区间最优解是列举区间每个数字作为第一个猜的数，然后一直猜猜到每个数都被猜过为止所花费的金额，这些金额的最小值就是这个区间的最优解。
//每个作为当前区间第一个猜的数所分割的区间，因为是分割，所以是左右区间，根据上面的定义，这个数的最后结果是左右区间最优解中最大的金额加上自身。而每个数都依此算，最后整个区间的最优解就是这些数的结果（金额）的最小值}f[l][r]=ret;}int getMoneyAmount(int n) {dfs(1,n);return f[1][n];}int f[202][202];//存当前区间的最优解，一维下标是左端，二维下标是右端
};

5.矩阵中的最长递增路径

class Solution {
public:bool check(int x, int y) {if (x < 0 || y < 0 || x >= m || y >= n)return false;return true;}
//检查是否越界void dfs(vector<vector<int>>& matrix, int x, int y){int ret = 1;for (int i = 0; i < 4; i++){int nx = x + dx[i], ny = y + dy[i];if (check(nx, ny) && matrix[x][y] < matrix[nx][ny]){
//满足不越界且递增的条件进入ifif (f[nx][ny] == 0)dfs(matrix, nx, ny);
//检查标记，剪枝。ret = max(ret, f[nx][ny] + 1);
//取最大}}f[x][y] = ret;
//记录当前结果ans = max(ans, f[x][y]);
//记录最大值return;}int longestIncreasingPath(vector<vector<int>>& matrix) {m = matrix.size();n = matrix[0].size();
//以每个数字为起点开始找，利用f数组，省略很多重复的dfs展开for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (f[i][j] == 0){dfs(matrix, i, j);}}}return ans;}int dx[4] = { 0,0,-1,1 };int dy[4] = { 1,-1,0,0 };int f[201][201];int n, m, ans = 0;
};