数组动态规划--LeetCode70爬楼梯LeetCode746最小花费爬楼梯《Blind-Stab》

本文主要是介绍数组动态规划--LeetCode70爬楼梯LeetCode746最小花费爬楼梯《Blind-Stab》,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

今天总结两道力扣网上非常经典的关于数组动态规划的题!-- 爬楼梯问题。

LeetCode70:

思路:

1、暴力破解,利用数学中学的组合,找出所有可能,但是太low了,并且无能弟弟写了发现超过一定数后算出的值是有问题的。

2、数组动态规划。

动态规划?怎么讲,其实和贪心算法一样,只是针对某一类型问题的思路思维常用解法。只是一种思想罢了,并没有具体的某个公式给你套,还是得自己归纳总结形成经验,具体问题具体分析。个人当前理解:所谓动态,无非就是  不是一层不变的,是其下一个状态与当前状态相关,当前状态影响下一个状态的一类问题。关键字就是状态,连续逐步进入的一个思路。知1求2,知2求3,知3求n的概念。废话不多说,解题。

解:

1、凡是这种动态规划类问题,首先我们要放小它,它相对其他问题来说是一个连续的问题。

2、连续,那我们就从最初始开始,求n,那我先看1,2,3,放小,先在123中找变化关系,进而推进。

3、n == 1,一种走法,没毛病。n == 2,两种,没毛病,和1有什么关系?多了一阶楼梯。n == 3,3种,没毛病,和2相比多了一阶楼梯。(是不是想到斐波那契数列了,还真是,但是这种规律能解出来,却没用我们的动态规划,没意义)

4、动态规划,关键是对比上下状态,去推理上一个状态和当前状态的关系,然后找到他们之间的联系。当然,更高深的词语我是表达不出来了。

5、动态规划,前面几个初始状态一般是要分开的,就是作为入口,开始,单独考虑。现在我们来看关键的,开始看出东西来的  n == 4 时,我们不知道它有多少种走法,但是我们可以联系 n == 1,2,3时。

6、对于 n == 4,相比3来说它只是多了一阶楼梯,而走到第4个阶梯,由于我们一次走楼梯的可能只有两种,要么加一走一阶楼梯,要么加二走二阶楼梯,那么可想而知,要走上第4阶楼梯,只有两种情况,①从第三阶梯走一步上去   ②从第二阶梯走两步上去。

7、那么就好了,假设走到第二节楼梯有dp[2]种可能,走到第三阶楼梯有dp[3]种可能,那么很明显,走到第四阶楼梯的可能dp[4]=dp[3] + dp[2];同样类比dp[5]、dp[6] ....dp[n];好么弟弟,真的是斐波那契数。

8、这样一分析会发现这种问题是很简单的,所谓动态规划,当前个人理解,无非就是某一状态会与它上一个状态相关联,连续下去,就是说因为给的条件,所以导致它直接与n相关。

废话也不必多少,代码如下:

class Solution {public int climbStairs(int n) {if (n == 1) {return 1;}int[] dp = new int[n + 1];dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

 

接下来看第二道

LeetCode746:

思路:

很明显,两道爬楼梯的,数组动态规划啊!

解:

1、又见爬楼梯,只不过这次多了个最小花费,在每个阶梯上加上了体力值,当然问的也不是可能性了,问的是这些可能性里面最小的花费值。

2、上题讲得很清楚了,n阶,那我放小,1,2,3考虑。

3、n == 1,家徒四壁,别无选择,最小花费体力值只能是cost[0]。n == 2,有人说,直接是cost[1]一步跨上去,确实是这样那  n  == 3,来,怎么解?有点不确定了,那我们就反着来分析。

4、其实还是一样的,我要跨上第n阶楼梯,那么cost[n-1]是加定了,也就是当前楼梯一定是会加上的。我们接着分析,我要跨上第n阶楼梯,和上面的一样,无非就是从n - 1阶楼梯跨一步上去,或者从n - 2阶楼梯跨两步上去,但现在要求最小花费,那么我的商议状态必然要满足也是走到它那个楼梯时也要是最小花费。好,结论出来了,同理,倒退,倒推,也就是没一步都要是最小花费,也就是从第一步开始就要是最小花费。

5、好,那这个结论该如何利用呢?我们回到1 2 3,我们要一开始就最小,是不是得先找到1的最小体力值花费,找到了1的才能找到2的,然后是3,,,最后是n。

6、又回到了上面的3,我们假设每走上每一阶梯的最小花费为spend[i],;第一阶梯spend[1] = cost[0];第二阶梯spend[2] = cost[1];好的,这是我们的初始化。

7、现在是第三阶梯,你可以从第一阶梯跨两步上去,也可以从第二阶梯跨一步上去,那你到底想咋样,那要看第三阶梯的前面两个阶梯也就是第一阶梯和第二阶梯哪一个的体力值花费少了,那就是Math.min(spend[1],[spend[2]) 。在加上你要去的第三阶梯的体力值花费cost[2],也就是  spend[2] = Math.min(spend[1],spend[0]) + cost[2];

8、好了,那式子可以出来了 ===> spend[n] = Math.min(spend[n-1],spend[n-2]) + cost[n];

9、然后,因为要跨上楼顶,而跨上楼顶,可以从n - 1,和 n - 2那里跨上去,所以,返回Math.min(spend[n-1],spend[n-2])就行了。

上代码:

class Solution {public int minCostClimbingStairs(int[] cost) {if(cost.length == 0)return 0;int [] spend = new int[cost.length];spend[0] = cost[0];spend[1] = cost[1];for(int i = 2; i < cost.length; i++){spend[i] = Math.min(spend[i-1],spend[i-2]) + cost[i];}int min = Math.min(spend[cost.length-1],spend[cost.length-2]);return min;}
}

 

总结:

1、所谓动态规划,关键字是动态,也就是改变的状态,那么关键就是要抓住状态两字,联系上下相邻状态,推理发现。

2、动态规划没什么可怕的,其实都是一类题,我们解题,不能抱着解决当前这个题的心态去解,是做一类题,不是做一个题。

3、也就是不是为了这道题而解题,咋说呢,就是解的是思维。

4、动态规划,无非就是找状态,逆推,先分析n,在退回1 2 3,在最后回到n,不离其综,不变其魂。

5、当然会涉及到一些最优问题,这点又和贪心算法有点像。比如这个最小体力花费。

6、最后,胜过万斤毒鸡汤,最好的两个词送给正在努力奋斗并看到这篇博客的陌生的你:

                                   坚持,加油!

 

这篇关于数组动态规划--LeetCode70爬楼梯LeetCode746最小花费爬楼梯《Blind-Stab》的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/234340

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计

前端 CSS 动态设置样式::class、:style 等技巧(推荐)

《前端CSS动态设置样式::class、:style等技巧(推荐)》:本文主要介绍了Vue.js中动态绑定类名和内联样式的两种方法:对象语法和数组语法,通过对象语法,可以根据条件动态切换类名或样式;通过数组语法,可以同时绑定多个类名或样式,此外,还可以结合计算属性来生成复杂的类名或样式对象,详细内容请阅读本文,希望能对你有所帮助...

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配