LintCode 爬楼梯题目分析代码小结

题目

假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?

样例 比如n=3,1+1+1=1+2=2+1=3,共有3中不同的方法,返回 3

分析

典型的动态规划问题。 我们假设到达第n级台阶的方法数为f(n),那么最后一步的时候,我们有两种选择,一是选择爬一步,那么这时候的方法数就是f(n-1),另一种选择是选择爬两步,方法数f(n-2).所以通过这个我们就可以得出f(n)的状态转移方程: f(n)=f(n-1)+f(n-2) 显然看到这里,我们可以利用递归求解这个问题。

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int climbStairs(int n) {
        // write your code here
      if (n == 0 || n == 1) return 1;  
        if (n < 0) return 0;  
        return climbStairs(n - 1) + climbStairs(n - 2); 
    }
}

climb.PNG

提交结果告诉我们超时了。所以我们不能用递归,需要采用效率更高的算法。 其实这类似于斐波那契数列,我们直接利用一个数组来记录f(n)就可以了。

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int climbStairs(int n) {
        // write your code here
      if (n == 1 || n==0) return 1;
      int[] f = new int[n+1];
      f[0] = 1;
      f[1] = 1;
      for(int i=2;i<=n;i++)
         f[i] = f[i-1] + f[i-2];
      return f[n];
    }
}

这种解法可以正确通过! 但我们可以更进一步优化算法,只采用两个变量即可 f(n) = f(n-1)+f(n-2) f(n-1) = f(n) - f(n-2) 利用这个关系, one = one + zero; zero = one - zero;

代码

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int climbStairs(int n) {
        // write your code here
      int one = 0;
      int two = 1;
      while(n>0)  {
          two=one+two;
          one=two-one;
          n--;
      }
      return two;
    }
}

小结

爬楼梯是一个典型的一维动态规划问题

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Deep Learning 笔记

MNIST__数字识别__SOFTMAX

本次MNIST的手写数字识别未采用input_data.py文件,想尝试一下用原始的数据集来运行这个DEMO。

1361
来自专栏计算机视觉life

OpenCV学习入门(四):RNG 伪随机问题

在我的上一篇博客《OpenCV学习入门(三):kmeans原理及代码 》中调试kmeans时发现一个问题:每次运行时,以下两行代码 int clusterCou...

2647
来自专栏漫漫深度学习路

tensorflow学习笔记(三十四):Saver(保存与加载模型)

Saver tensorflow 中的 Saver 对象是用于 参数保存和恢复的。如何使用呢? 这里介绍了一些基本的用法。 官网中给出了这么一个例子: ...

4048
来自专栏小樱的经验随笔

qsc oj 22 哗啦啦村的刁难(3)(随机数,神题)

哗啦啦村的刁难(3) 发布时间: 2017年2月28日 20:00   最后更新: 2017年2月28日 20:01   时间限制: 1000ms   内存限制...

2889
来自专栏机器之心

入门 | GPU是如何优化运行机器学习算法的?

39614
来自专栏深度学习之tensorflow实战篇

python下Matplotlib绘图案例与常见设置简介

首先一幅Matplotlib的图像组成部分介绍。 基本构成 在matplotlib中,整个图像为一个Figure对象。在Figure对象中可以包含一个或者多个A...

4616
来自专栏智能算法

深度学习三人行(第2期)---- TensorFlow爱之再体验

上一期,我们一起学习了TensorFlow的基础知识,以及其在线性回归上的初体验,该期我们继续学习TensorFlow方面的相关知识。学习的路上,我们多多交流,...

35610
来自专栏null的专栏

挑战数据结构和算法面试题——最大间隔

题目来自伯乐在线,欢迎有不同答案的同学来一起讨论。 ? 分析: 本题首先需要理解清楚最大间隔的最小: 最初的间隔为:[1,1,4,1],此时最大间隔为4 删...

3023
来自专栏后端技术探索

一致性hash算法清晰详解!

consistent hashing 算法早在 1997 年就在论文 Consistent hashing and random trees 中被提出,目前在 ...

812
来自专栏ATYUN订阅号

Tensorflow 1.3.0版本的变更概述

尽管距离Tensoflow 1.2.1版本发布才仅仅一个月,但是1.3.0版本中的软件已经发生了很多变化。开发人员可以在Tensorflow的Github页面上...

3727

扫码关注云+社区

领取腾讯云代金券