阜宁有做网站的吗,更新php wordpress,中山网站网站建设,广州做大型网站建设目录
斐波那契数
不同路径
最长递增子序列
猜数字大小II
矩阵中的最长递增路径 声明#xff1a;下面将主要使用递归记忆化搜索来解决问题#xff01;#xff01;#xff01;
斐波那契数
题目 思路
斐波那契数的特点就是除了第一个数是0#xff0c;第二个数是1下面将主要使用递归记忆化搜索来解决问题
斐波那契数
题目 思路
斐波那契数的特点就是除了第一个数是0第二个数是1其余的数都是前两个数的和。
显然我们很容易用递归实现但是会超时的因为计算第n个位置的斐波那契数的大小时会重复很多次的计算某些位置的斐波那契数因此如果我们能记录下已经计算过的位置对应的斐波那契数时当再次需要该位置的斐波那契数时就不用再重复的进行计算了。
代码
class Solution {long long memo[101];
public:int fib(int n) {memset(memo,-1,sizeof memo);// std::fill(memo, memo 101, -1);return dfs(n);}int dfs(int n){if(memo[n]!-1)return memo[n];if(n0 || n1){memo[n]n;return memo[n];}memo[n](dfs(n-1)dfs(n-2))%1000000007;return memo[n];}
};class Solution {
// public:
// int fib(int n) {
// if(n0 || n1)
// return n;
// vectorint dp(n1);
// dp[0]0,dp[1]1;
// for(int i2;in;i)
// dp[i](dp[i-1]dp[i-2])%1000000007;
// return dp[n];
// }
// };
不同路径
题目 思路
本道题很容易使用递归实现但是会超时原因同上一道题一样会大量重复的计算一些以某些位置为起点到终点的路径数而且时间复杂度是呈指数级别的因此我们可以和上一道题一样如果将已经计算过的以某些位置为起点到终点的路径数记录下来当再次求以这些位置为起点到终点的路径数时直接使用即可避免了大量的重复计算。
代码
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint memo(m1,vectorint(n1));return dfs(m,n,memo);}int dfs(int x,int y,vectorvectorint memo){if(memo[x][y]!0) return memo[x][y];if(x0|| y0) return 0;if(x1 y1){memo[x][y]1;return 1;}else{memo[x][y]dfs(x-1,y,memo)dfs(x,y-1,memo);return memo[x][y];}}
};class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m1,vectorint(n1));// dp[0][1]1;dp[1][0]1;for(int i1;im;i){for(int j1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];}}return dp[m][n];}
};
最长递增子序列
题目 思路
这道题已经在之前的博客中写过了之前使用的是动态规划和贪心二分之前的动态规划是从前往后分析的下面将使用递归记忆化搜素以及从后往前的分析的动态规划。
递归记忆化搜素
从头到尾扫描数组分别计算以该位置为起点的最长递增子序列的长度并把每次计算好的结果进行记录当下次再次用到以已记录位置为起点的最长递增子序列的长度时直接拿已经计算好的结果即可避免了不少重复的计算。
从后往前的分析的动态规划
可以说是在分析前面的递归记忆化搜素方法的基础上摸索出来的如何定义状态表示和状态转移方程等这里不再赘述可以参考之前的博客。
代码
class Solution {
public:int lengthOfLIS(vectorint nums) {//记忆化搜索int ret1;vectorint memo(nums.size());for(int i0;inums.size();i)retmax(ret,dfs(i,nums,memo));return ret;}int dfs(int pos,vectorint nums,vectorint memo){if(memo[pos]!0) return memo[pos];int k1;for(int ipos1;inums.size();i)if(nums[i]nums[pos])kmax(k,dfs(i,nums,memo)1);memo[pos]k;return k;}
};//递归记忆化搜素 class Solution {
public:int lengthOfLIS(vectorint nums) {int nnums.size();vectorint dp(n,1);for(int in-1;i0;i--)for(int ji1;jn;j){if(nums[i]nums[j])dp[i]max(dp[i],dp[j]1);}return *max_element(dp.begin(),dp.end());}
};//动态规划
猜数字大小II
题目 思路
上面之所以没有截示例是因为示例比较长而且文字描述很多比较容易看晕下面也是采用递归记忆化搜素来解决因为如果只使用递归会超时因为会大量的重复计算相同位置的值如果能够将每次计算好的值保存起来下次使用时直接取就能够较少大量的操作更佳。
从头到尾扫描整个数组分别计算以该位置为起点的最大花费然后计算所有起始位置的最大花费的最小值。
代码
class Solution {int memo[201][201];
public:int getMoneyAmount(int n) {return dfs(1,n);}int dfs(int left,int right){if(leftright) return 0;if(memo[left][right]!0) return memo[left][right];int retINT_MAX;for(int headleft;headright;head){int xdfs(left,head-1);int ydfs(head1,right);retmin(ret,headmax(x,y));}memo[left][right]ret;return ret;}
};
矩阵中的最长递增路径
题目 思路
下面也是采用递归记忆化搜素来解决因为如果只使用递归会超时因为会大量重复计算以某位置为起点的最长递增路径如果能够记录下以某位置为起点的最长递增路径当下次使用时直接取即可就能够减少大量的重复计算以示例1为例比如就以【2】【1】位置的1为起始位置计算时会有一条向上到6的路径但是如果已经计算过以这个6为起始位置的最长递增路径的长度可以直接使用就不用再重复计算了。 代码
class Solution {
public:int n,m;int maxlen[201][201];int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};int longestIncreasingPath(vectorvectorint matrix) {int ret0;nmatrix.size(),mmatrix[0].size();for(int i0;in;i)for(int j0;jm;j)retmax(ret,dfs(matrix,i,j));return ret;}int dfs(vectorvectorint matrix,int i,int j){if(maxlen[i][j]!0) return maxlen[i][j];int ret1;for(int k0;k4;k){int xidx[k];int yjdy[k];if(x0 xn y0 ym matrix[x][y]matrix[i][j])retmax(ret,dfs(matrix,x,y)1);}maxlen[i][j]ret;return ret;}
};
