做circrna的网站,网页设计课程培训班,牛商网网站后台,该网站在工信部的icp ip地址java数据结构与算法刷题目录#xff08;剑指Offer、LeetCode、ACM#xff09;-----主目录-----持续更新(进不去说明我没写完)#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 很多人觉得动态规划很难#xff0c;但它就是固定套路而已。其实动态规划只…java数据结构与算法刷题目录剑指Offer、LeetCode、ACM-----主目录-----持续更新(进不去说明我没写完)https://blog.csdn.net/grd_java/article/details/123063846 很多人觉得动态规划很难但它就是固定套路而已。其实动态规划只不过是将多余的步骤提前放到dp数组中就是一个数组只不过大家都叫它dp达到空间换时间的效果。它仅仅只是一种优化思路因此它目前的境地和线性代数一样----虚假的难。 想想线性代数在国外留学的学生大多数不觉得线性代数难理解。但是中国的学生学习线性代数时完全摸不着头脑一上来就是行列式和矩阵根本不知道这玩意是干嘛的。线性代数从根本上是在空间上研究向量抽象上研究线性关系的学科。人家国外的教科书都是第一讲就帮助大家理解研究向量和线性关系。反观国内的教材直接把行列式搞到第一章。搞的国内的学生在学习线性代数的时候只会觉得一知半解觉得麻烦完全不知道这玩意学来干什么。当苦尽甘来终于理解线性代数时干什么的时候发现人家国外的教材第一节就把这玩意讲清楚了。你只会大骂我们国内这些教材什么狗东西以上是自己学完线性代数后的吐槽我们同学无一例外都这么觉得。 而我想告诉你动态规划和线性代数一样我学完了才知道它不过就是研究空间换时间提前将固定的重复操作规划到dp数组中而不用暴力求解从而让效率极大提升。 但是网上教动态规划的兄弟们你直接给一个动态方程是怎么回事和线性代数一上来就教行列式和矩阵一样纯属恶心人。我差不多做了30多道动态规划题目才理解动态方程只是一个步骤而已而这已经浪费我很长时间了我每道题都一知半解不理解过程及其痛苦。最后只能重新做。动态规划一定是优先考虑重复操作与dp数组之间的关系搞清楚后再提出动态方程。而你们前面步骤省略了不讲一上来给个方程不是纯属扯淡吗我推荐研究动态规划题目按5个步骤从上到下依次来分析 DP数组及下标含义递推公式dp数组初始化数组遍历顺序双重循环及以上时才考虑dp数组打印分析思路是否正确相当于做完题检查一下 先理解题目细节 想象这样一个场景我们是小偷从第一栋挨个考虑偷还是不偷如果偷那就是身上已经偷了多少这一栋能偷多少。如果不偷那就是身上已经偷了多少。 题目给我们的数组代表每个房子有多少钱而且相邻的房子不能都偷只能偷不相邻的。例如2,1,1,2 这个序列显然不触发警报的前提下不偷相邻的----偷第一个和第4个为能偷到的最多的钱怎么偷才能偷到最多呢当然是保证最大获利情况下能偷的都偷了而且不能触发警报。我们每个房子都单独考虑偷还是不偷而且只需考虑它前面的房子因为我们要能偷的都偷 若要偷当前房子那么前面相邻的不能考虑只能考虑再前面一个也就是当前房子的金额加上除了前面一个相邻的房子外已经偷了多少。若不偷当前房子那么前面偷了多少到这个房子就还有多少金额不变 解题思路 暴力求解的思想就是回溯算法枚举每一种情况拿到最大值显然会做大量无效运算。但是如果我们预先将其存储到dp数组就可以直接通过dp[x], 获取dp数组中指定位置x的体力花费而不用枚举。典型的动态规划题目 动态规划思考5步曲 DP数组及下标含义 我们要求出的是到了某个房子后最大情况下偷了多少钱那么dp数组中存储的就是最大情况下偷了多少钱。要求出谁的最大情况下偷了多少。显然是到达某个房子后那么下标就是代表现在到了哪个房子也就是代表到了某一栋房子后的最大已偷取的金额。显然只需要一个下标即可表示故这道题的dp数组只需要一维数组 递推公式 由题意可知每个房子都可以选择偷与不偷选择最大值。而第一个房子肯定要偷它才能获得最大值。而第二个房子因为它前面没有不相邻的房子所以它要么不偷也就是只偷第一个房子。要么选择偷第二个房子而第一个房子不偷然后选择最大情况。 故第一个房子固定为F(0) 第一个房子金额。第二个固定为F(1) max(第一个房子金额第二个房子金额) 之后每一栋都需要判断它偷还是不偷以及前面不相邻的房子。如果偷就要考虑前面不相邻的自己这栋能偷多少钱。不偷那么前一栋相邻的它肯定考虑一下。而前面的房子怎么考虑的是前面房子的事它们也考虑过了偷还是不偷。我们只考虑当前这栋是偷还是不偷因此可以得到从第三栋开始递推公式为偷或者不偷选择最大值 F(n) max( F(n-2)nums[n] , F(n-1) ) dp数组初始化 数组遍历顺序因为这个数列是一维的只需要一重循环无需考虑这个打印dp数组自己生成dp数组后将dp数组输出看看是否和自己预想的一样。 代码:时间复杂度O(n).空间复杂度O(n) class Solution {public int rob(int[] nums) {int length nums.length;//有多少栋房子int dp[] new int[length];//dp数组dp[0] nums[0];//第一栋只能选择偷它//第二栋可以选择偷那么第一栋不能偷或者不偷只偷第二栋第一栋不偷无需考虑前面不相邻的if(length2) dp[1] Math.max(nums[0],nums[1]);//第三栋开始不仅仅要考虑偷还是不偷还要考虑前面不相邻的for(int i 2;ilength;i){//如果这一栋不偷则前面偷了多少就是多少也就是到上一栋时有多少就有多少dp[i-1]//如果这一栋要偷则前面不相邻的偷了多少 这一栋有多少 为偷完这一栋拿到的钱dp[i] Math.max(dp[i-2]nums[i],dp[i-1]);//我们只考虑最大情况}return dp[length-1];//返回偷到最后一栋时偷到的最大金额}
}学有余力的同学可以尝试这个方法将空间复杂度变为常数级-----------------代码:时间复杂度O(n).空间复杂度O(1) 将dp数组优化掉换成3个变量滚动执行。将dp[0]换成first。dp[1]换成second. 也就是first永远指向当前栋的前面不相邻的second永远指向前面相邻的。 class Solution {public int rob(int[] nums) {int length nums.length;//有多少栋房子int first nums[0],second nums[0];//第一栋只能选择偷它//第二栋可以选择偷那么第一栋不能偷或者不偷只偷第二栋第一栋不偷无需考虑前面不相邻的if(length2) second Math.max(nums[0],nums[1]);//第三栋开始不仅仅要考虑偷还是不偷还要考虑前面不相邻的for(int i 2;ilength;i){int temp second;second Math.max(firstnums[i],second);//我们只考虑最大情况first temp;}return second;//返回偷到最后一栋时偷到的最大金额}
}
