榆林网站建设电话,帮别人做违法网站会怎么样,百度网站收录查询地址,平台电商是什么意思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数组打印分析思路是否正确相当于做完题检查一下 拿到比较抽象的题先列出前几项结果尝试看出问题的本质很多比较抽象的题本质都很简单抓住问题的本质那么可以做到解决1道题扩展到解决一类问题 n 0时结果为0n 1时结果为1n 2时结果为2n 3时结果为3n 4时结果为5 可见 这道题的规律0 1 2 3 5… 和斐波那契数列的0 1 1 2 3 5…非常像 什么是斐波那契数列 斐波那契数列第一个值是0第二个值是1剩下的元素是它前两个元素和例如0 1 1 2 3 5… 可见除了最开始的两个固定为0和1外其余每一个元素都是前两个元素的和。也就是说这玩意一看就是固定的一套值如果每次都重新生成就太暴力了。动态规划的思想就是将生成的过程就生成一次之后再用直接从dp数组中拿。从而大大提升效率 解题思路 暴力求解的思想就是定义3个或者2个变量然后累加以获得指定位置的斐波那契数。每次都需要从头开始累加但是如果我们预先将其存储到dp数组就可以直接通过dp[x], 获取dp数组中指定位置x的对应斐波那契数而不用每次都从头计算。但是这道题从第4个元素开始才符合斐波那契数列的规则因此我们这道题可以用斐波那契数列思想但不能照搬可见这道题前3个为固定值 0 1 2 剩下的都是当前元素的前两项的和。 动态规划思考5步曲 DP数组及下标含义 DP数组存储我们分析的类似斐波那契数列的数列这个数列是一维线性的所以只需一维数组存储。下标代表数在数列中的位置。dp[0] 0,dp[1] 1,dp[2]2是头三个固定值斐波那契数列头两个是固定值dp[3]开始每个元素是前两个数组元素的和。即可生成对应数列的dp数组。 递推公式 既然知道了DP数组就是存储的类似斐波那契数列的数列那么递推公式很显然就是当前元素前两个元素的和。F(n) F(n-1)F(n-2)。 而且F(0) 0,F(1)1,F(2) 2这是这个数列的特性前三个值固定为0,1,2. dp数组初始化 数组遍历顺序因为这个数列是一维的只需要一重循环无需考虑这个打印dp数组自己生成dp数组后将dp数组输出看看是否和自己预想的一样。 代码 class Solution {public int climbStairs(int n) {int length n3?n:3;//避免n给的太小例如n 3时下面的dp[2] 2; 这条代码会下标越界//初始化DP数组一维数组即可头3个元素固定为0,1,2int dp[] new int[length1]; dp[0] 0; dp[1] 1;dp[2]2;//其余元素为它的前两个元素的和for(int i 3;in ; i){dp[i] dp[i-1]dp[i-2];}return dp[n];}
}
