美文网首页
由一道简单“动态规划”算法题而引发的思考

由一道简单“动态规划”算法题而引发的思考

作者: 理学星球 | 来源:发表于2019-12-31 18:22 被阅读0次

假如你正在爬楼梯。需要n阶你才能到达楼顶。每次你只可以爬1或2个台阶,你有多少种方法可以爬到楼顶?

由于算法题做的比较少,我大概归纳出一套解题思路(不知道适不适合全部):

1、写出具体示例

1层 1    一种

2层 1+1 2    二种

3层 111 12 21    三种

4层 1111 121 211 112 22    五种

5层 11111 221 212 122 1112 2111 1211 1121 八种

2、找出数学关系

这道题在1层和2层看不出数学关系,我觉得大部分题也是这样的。观察得出f(n)=f(n-1)+f(n-2)。等做题做多了再总结下常见的数学关系

3、编程序

首先想到递归,由于递归时间复杂度较大,不可取

用for循环解决

我们可以利用for循环和数组解决。

细节:别忘了前面的if(n=0)if(n=1)if(n=2)的返回值

相关文章

  • 由一道简单“动态规划”算法题而引发的思考

    假如你正在爬楼梯。需要n阶你才能到达楼顶。每次你只可以爬1或2个台阶,你有多少种方法可以爬到楼顶? 由于算法题做的...

  • 面试常见算法——爬楼梯

    又到了每周的算法时间了,今天给大家带来一道很经典,又很简单,又比较适合对动态规划极度恐惧的童鞋,做动态规划的题,一...

  • 动态规划思想的思考

    对动态规划的思考 如何确定一类的算法问题可以用动态规划的方式,首先就是抓住算法题的最优结果,是否可以从前往后,从上...

  • 由一道题引发的思考

    同事发来信息: “一双鞋进价70元,82元售出。收了100元可老板事后发现是假币。问他在这件事上共赔了多少? 这是...

  • 最大子序和

    这道题是一道经典算法题,也是清华考研的题目,使用动态规划(不太理解)来解决,时间复杂度为O(n)。 题目:给定一个...

  • leetcode-打家劫舍(I,II,III)-动态规划

    又做了一次,还是没想出来。是一道很简单的动态规划,可惜自己一直不理解动态规划。 把上一道题的结果,用两次。由于围城...

  • Best Time to Buy and Sell Stock

    tags: 算法, LeetCode, swift, 动态规划 这是最近在学算法中完成的第一个系列题,系列题...

  • 初探动态规划——LeetCode找零钱问题

    1.简介: 在leetcode上刷题的时候,遇到了一道找零钱的动态规划题,后台测试用例很变态,必须把算法优化的很好...

  • 4. 动态规划算法

    1. 动态规划算法总结2. 漫画:什么是动态规划?3.算法之动态规划4. 动态规划-算法

  • 动态规划——打家劫舍

    这道题也算是一道挺经典的题,即使不了解动态规划的人肯定也见过这道题。先来看代码 这里还有第二种解法,算法思想依然是...

网友评论

      本文标题:由一道简单“动态规划”算法题而引发的思考

      本文链接:https://www.haomeiwen.com/subject/vklioctx.html