网站空间多少钱一年,怎样做博客网站,国内做免费的视频网站有哪些,深圳高端网站定制公目录
1. 斐波那契数#xff08;easy#xff09;
那么这里就画出它的决策树 #xff1a;
解法一#xff1a;递归暴搜 解法二#xff1a;记忆化搜索
解法三#xff1a;动态规划
1.暴力解法#xff08;暴搜#xff09;
2.对优化解法的优化#xff1a;把已经计算过的…目录
1. 斐波那契数easy
那么这里就画出它的决策树
解法一递归暴搜 解法二记忆化搜索
解法三动态规划
1.暴力解法暴搜
2.对优化解法的优化把已经计算过的值存起来。
那么问题来了
2. 不同路径medium) 解析
解法一暴力
解法二记忆化搜索
添加备忘录
解法三随手改动态规划
3. 最⻓递增⼦序列medium
解析
解法一暴搜
决策树暴搜dfs
记忆化暴搜
解法二记忆化搜索
解法三动态规划
4. 猜数字⼤⼩IImedium
解析
解法一暴搜dfs
解法二记忆化搜索
其实大差不差就是专门添加一个备忘录
5. 矩阵中的最⻓递增路径hard
解法一暴搜
解法二记忆化搜索
总结一下吧~学到现在递归章节也算是告一段落了我个人的进步确实有了质的变化我自己能感受到对于这一专题可以很明显的看出在遇到重复子问题并且求关于路径个数最长长度多少次数之类的问题都是要对整个决策树进行完整的遍历和取最值但是在遍历过程种都会遇到很多重复遍历的问题对于这种重复遍历的问题的次数我们只需要往动态规划方面考虑的思路这里不同于前几个章节的直接深度优先遍历利用visit数组来判断还需不需要进入下一层那个属于floodfill算法要求分块的面积或者分块的个数所以还是要好好进行区分总结 为了能引入记忆化搜索的概念和体现它的完美性这里引入一个例题来进行描述
1. 斐波那契数easy 斐波那契数列的引入相比前面那些暴搜的题目还是要简单很多但是也不能小看这一题的简单程度一般难的题目总是有很多简单的小块来进行综合的所以有这题引入可以分别解决关于 暴搜 - 记忆化搜索 - 动态规划 的过度, 那么这里就画出它的决策树 这里通过这个决策树来求解斐波那契数列的暴力解就是不断的递归到最后一层和就进行求解d[0] 和 d[1] 的值的大小
解法一递归暴搜
class Solution {
public:int fib(int n) {return dfs(n);}int dfs(int n){if(n0||n1) return n;return dfs(n-1)dfs(n-2);}
}; 虽然这里的暴搜过程十分简单但是当我们看到这里的时间复杂度上以及这个决策树上有着非常多的重复步骤列入这个决策树上进行展开想求d[5]就得知道d[4]d[3],依次类推那么想知道d[4] 就又要知道d[3]d[2] 那么这里就会有很多重复性的步骤会让时间复杂度大大增加 那么在此基础上我们只需要添加一个备忘录让每次进行第一次递归的值能够存入到备忘录那么只要后面再次遍历到该数的时候就能够直接得到该数此时加入遍历的深度是O(N),那么就要递归n层在进行返回才能再次得到该值但是如果采用记忆化搜索得到该值只需要在O(1)的时间内进行查找该值即可。 解法二记忆化搜索
什么是带备忘录的递归只需要在O(1)时间内就能够再次得到该值
如何实现记忆化 1.添加一个备忘录 实现可变参数返回值就是 下标 跟 返回值 的映射 2.递归每次返回的时候将结果放到备忘录里面 3.在每次进入递归的时候往备忘录里面瞅一瞅 那么实现备忘录就需要一个一维数组进行下标与返回值的映射即可
memo[100]; 这里要对memo数组进行初始化初始化要对该数组实现在后面递归返回值存入时不会出现的数保证不会出现并没有存入该值却被取出值的情况 memset(memo,-1,sizeof(memo)); 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(n0||n1) return n;memo[n]dfs(n-1)dfs(n-2);return memo[n];}
};
1.这里就要对全局变量添加一个备忘录让后进行初始化为-1
2.在入口处就要判断当前下标为n处是否在备忘录中出现过若出现过就直接取走否则就进行递归在后面第一次出现的时候进行添加
3.因为只有在最后一层的时候有明确的返回值这样遍历到最后一层可以直接进行返回但是memo[n]在递归过程中第一次出现的结果全部都添加到备忘录内这样就不会出现第二次递归到最后一层的结果然后进行第一次添加后进行最后的返回该层的memo[n]; 解法三动态规划 从动态规划内的步骤可以看出动态规划与记忆化搜索都是一一对应的也可以说记忆化搜索其实也就是另一种形式的普通动态规划。
动态规划 和 记忆化搜索的本质
1.暴力解法暴搜
2.对优化解法的优化把已经计算过的值存起来。 在《算法导论》里面记忆化搜索 vs 常规动态规划 - 统称为动态规划 递归 地推(循环)
class Solution {
public:int dp[31];int fib(int n) {dp[0]0,dp[1]1;for(int i2;in;i)dp[i]dp[i-1]dp[i-2];return dp[n];}
};
动态规划只要准备好状态转移方程就能够进行解答问题。
那么问题来了 1.所有的递归暴搜、深搜都能改成记忆化搜索嘛 不是的只有在递归的过程中出现了大量完全相同的问题时才能用记忆化搜索的方式优化。 2.带备忘录的递归 vs 带备忘录的动态规划 vs 记忆化搜索 都是一回事 3.自顶向下 vs 自顶向上 所以对于记忆化搜索的问题也就是说在画出决策树或者递归展开图的时候发现很多重复性的子递归那么此时就用一个备忘录进行记录当前值然后进行记录当前值以便后续直接进行查找不用再次进行递归。 2. 不同路径medium)
题目意思很简单就是求出原点到右下角的所有路径个数 解析
随便找一个点想要求出到达当前位置的所有路径个数那么就是 dfs(i,j)dfs(i-1,j)dfs(i,j-1); 那么原点这个位置就不能从(0,0)开始要从(1,1) 开始。所以要为这个矩阵加一行一列。
那么当i0 或者 j0 的时候就都是不能成立的时候因为在这上面都是不能满足条件的。 解法一暴力
class Solution {
public:int uniquePaths(int m, int n) {return dfs(m,n);}int dfs(int i,int j){if(i0||j0) return 0;if(i1j1) return 1;return dfs(i-1,j)dfs(i,j-1);}
}; 就只是利用暴搜的方式但这个会超时所以要对它进行记忆化改进。 解法二记忆化搜索
class Solution {
public:int memo[101][101];int uniquePaths(int m, int n) {memset(memo,-1,sizeof(memo));return dfs(m,n);}int dfs(int i,int j){if(memo[i][j]!-1) return memo[i][j];if(i0||j0) return 0;if(i1j1) return 1;memo[i][j]dfs(i-1,j)dfs(i,j-1);return memo[i][j];}
};
添加备忘录 1.就是在进入dfs的时候观察有没有满足已经存在备忘录的条件的值。 2.在当前值被返回之前存入备忘录 解法三随手改动态规划
class Solution {
public:int uniquePaths(int m, int n) {vectorvectorint dp(m1,vectorint(n1));dp[1][1]1;for(int i1;im;i){for(int j1;jn;j){if(i1j1) continue;dp[i][j]dp[i-1][j]dp[i][j-1];}}return dp[m][n];}
};
可以看的出来思路完全就是跟记忆化搜索大差不差所以对于暴搜改记忆化记忆化改动态规划简直不要太方便。 3. 最⻓递增⼦序列medium
题目意思就跟标题一样简单只需要求出最长子序列即可。 解析 解法一暴搜 决策树暴搜dfs class Solution {
public:int n,ret1;bool visit[2501];int lengthOfLIS(vectorint nums) {nnums.size();for(int i0;in;i){dfs(nums,i,1);}return ret;}void dfs(vectorint nums,int pos,int k){for(int ipos1;in;i){if(visit[i]falsenums[pos]nums[i]){k;visit[i]true;retmax(ret,k);dfs(nums,i,k);visit[i]false;k--;}}}
}; 记忆化暴搜 利用动态规划的思想但是这是个决策树要往记忆化的方向去靠近那么就是从上往下的递归然后求值并存入备忘录。这里只考虑暴搜的结果传入从i位置开始的结果进去后开始考虑下一个值是选取哪一个位置的值进行判断条件因为进入dfs后当层的ret就都是要求出当前层ret的最大值判断条件 if(nums[i]nums[pos]) 因为dfs要返回当前层后面的最长子序列所以用ret接受dfs的返回值 retmax(ret,dfs(nums,i)1); class Solution {
public:int lengthOfLIS(vectorint nums) {int ret0;for(int i0;inums.size();i) retmax(ret,dfs(nums,i));return ret;}int dfs(vectorint nums,int pos){int ret1;for(int ipos1;inums.size();i){if(nums[i]nums[pos]){retmax(ret,dfs(nums,i)1);}}return ret;}
}; 那么这个暴搜绝对会超时因为在整个非常大的树的时候会进行完全展开出现很多重复性的子问题会对很多已经被展开的树再次进行展开时间复杂度大大增加。 解法二记忆化搜索
那么就要开始考虑记忆化搜索来添加备忘录这里memo弄成全局和传参都一个样传参数也是要加引用就相当于全局变量。 添加备忘录 1.就是判断当前位置pos的值是否存在备忘录里面这样直接去pos后面的最长的子序列长度。 2.ret还是照样要求出当前层的最大值然后再最后返回ret的时候要对ret存入备忘录的操作这样在后面再次要展开pos层的时候能直接再备忘录内找到。 class Solution {
public:int lengthOfLIS(vectorint nums) {int nnums.size();vectorint memo(n);int ret0;for(int i0;inums.size();i) retmax(ret,dfs(nums,i,memo));return ret;}int dfs(vectorint nums,int pos,vectorint memo){if(memo[pos]) return memo[pos];int ret1;for(int ipos1;inums.size();i){if(nums[i]nums[pos])retmax(ret,dfs(nums,i,memo)1);}memo[pos]ret;return ret;}
}; 解法三动态规划 记忆化搜索改动态规划其实再两个代码内可以看出是一一对应的我们要求出当前位置的最长子序列就要通过最后面的值往前遍历来从长度为1开始往前求才能更好的求出dp[i]位置的长度。 那么当从最后一个数往前求的时候唯一可以顾及到的就是当前数的后面的所有数。也就是当前位置的决策树。进行展开就是一个小的决策树。就是dp[i],dp[j]1取最大值此时的for(j)是从nums[i]后面的所有值开始的。 class Solution {
public:int lengthOfLIS(vectorint nums) {int nnums.size();vectorint dp(n,1);//依赖后面的值所以从后往前填表int ret0;for(int in-1;i0;i--){for(int ji1;jn;j)if(nums[j]nums[i]) dp[i]max(dp[i],dp[j]1);retmax(ret,dp[i]);}return ret;}
}; 4. 猜数字⼤⼩IImedium 题目意思有点难理解推荐直接往后看 解析
题目意思 玩这个游戏要准备的最少的本金如果猜错了就要给但钱猜错数字的前求出最少需要多少前可以完全获得胜利直到猜对为止。 那么为了找出最所要最少的钱那么就要暴力的枚举所有情况然后找出最少的钱能够获胜的时候 那么画出决策树后大概就是再一个区间随机选择一个数让系统告诉我是大了还是小了如果大了就递归到下一层再选择一个比上一层要小的值如果小了就到下一层选一个比上一层大的值。 然后进行返回到上一层【xy】都是左子树或者右子树所需最小的钱在对【x,y】取最大值因为只有取了最大值才能保证准备的钱满足所有的情况。 解法一暴搜dfs 考虑两种边界条件当i1的时候取【left , right】 - [1,0] 这种取值范围不合法 直接返回0 当i2 的时候取值范围是[left,right] - [1,1] 说明已经只有最后一个值了直接返回0不用再往后继续进行取值。 if(leftright) return 0; 暴搜dfs(1,n) 传入可以随机取值的区间范围然后进行猜数字游戏
猜出所有数字的情况head作为头节点如果大了就定义x去[left,head-1]位置去找如果小了就定义y去[head1,right]区间去找然后都返回的是两边的最小值让用到的钱最小然后对两边的值取最大max(x,y) 这样能保证这个最小值里面的最大值可以让当前层的所有花费都被满足但是当前层后续有很多种随机取值的方式所以我们要考虑到最便宜的一种就是最后当前层随机取值的所有情况都要取min class Solution {
public:int getMoneyAmount(int n) {return dfs(1,n);}int dfs(int left,int right){if(leftright) return 0;int retINT_MAX;for(int headleft;headright;head){int xdfs(left,head-1);int ydfs(head1,right);retmin(headmax(x,y),ret);}return ret;}
}; 解法二记忆化搜索 其实大差不差就是专门添加一个备忘录 只要写出来暴搜的过程改成记忆化简直易如反掌 1.添加备忘录然后判断当前值的取值范围[left][right]是否再备忘录内出现过 2.每次再该层的取值范围进行返回前先存入到备忘录内 memo[left][right]ret; class Solution {
public:int memo[201][201];int getMoneyAmount(int n) {return dfs(1,n);}int dfs(int left,int right){if(leftright) return 0;if(memo[left][right]) return memo[left][right];int retINT_MAX;for(int headleft;headright;head){int xdfs(left,head-1);int ydfs(head1,right);retmin(headmax(x,y),ret);}memo[left][right]ret;return ret;}
}; 5. 矩阵中的最⻓递增路径hard 题目意思很简单就是要求出任意一点出发能够找出的最长的递增路径的长度。 解析 解法一暴搜 不用想肯定会超时但是思路是简单的只需要再主函数内任意传入一个位置的值然后开始遍历上下左右开始返回能够进入当前位置的最大长度一直让ret取到当前位置的最大长度即可。 class Solution {
public:int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};int n,m;int longestIncreasingPath(vectorvectorint matrix) {mmatrix.size(),nmatrix[0].size();int ret0;for(int i0;im;i){for(int j0;jn;j){retmax(ret,dfs(matrix,i,j));}}return ret;}int dfs(vectorvectorint matrix,int i,int j){int ret1;for(int k0;k4;k){int xdx[k]i;int ydy[k]j;if(x0xmy0ynmatrix[x][y]matrix[i][j]){retmax(ret,dfs(matrix,x,y)1);}}return ret;}
}; 解法二记忆化搜索 跟上面题目一样只需要添加上备忘录 1.进入dfs判断是否存在当前值再备忘录内如果存在就直接返回不存在就进行添加 2.每次到dfs函数底部进行返回前只需要将当前值进行存入即可。 class Solution {
public:int dx[4]{0,0,1,-1};int dy[4]{1,-1,0,0};int n,m;int memo[201][201];int longestIncreasingPath(vectorvectorint matrix) {mmatrix.size(),nmatrix[0].size();int ret0;for(int i0;im;i){for(int j0;jn;j){retmax(ret,dfs(matrix,i,j));}}return ret;}int dfs(vectorvectorint matrix,int i,int j){if(memo[i][j]) return memo[i][j];int ret1;for(int k0;k4;k){int xdx[k]i;int ydy[k]j;if(x0xmy0ynmatrix[x][y]matrix[i][j]){retmax(ret,dfs(matrix,x,y)1);}}memo[i][j]ret;return ret;}
}; 总结一下吧~学到现在递归章节也算是告一段落了我个人的进步确实有了质的变化我自己能感受到对于这一专题可以很明显的看出在遇到重复子问题并且求关于路径个数最长长度多少次数之类的问题都是要对整个决策树进行完整的遍历和取最值但是在遍历过程种都会遇到很多重复遍历的问题对于这种重复遍历的问题的次数我们只需要往动态规划方面考虑的思路这里不同于前几个章节的直接深度优先遍历利用visit数组来判断还需不需要进入下一层那个属于floodfill算法要求分块的面积或者分块的个数所以还是要好好进行区分总结 希望对你也有帮助~
