动态规划中篇:爬楼梯

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。

01

你会学到什么?

在前面的两个推送:

LeetCode实战:动态规划算法是怎么一回事

动态规划:括号知多少

我们通过两个实际问题,《装水做多的容器》和《括号知多少》,初步对动态规划有了一个初步了解。

在本推送中,我们将解决以下两个问题:

  1. 动态规划牺牲空间换来了什么?
  2. 动态规划如何提升时间性能的?
  3. 再举动态规划的一个实际例子

02

动态规划相关理论

动态规划的定义

动态规划的英文名称为:dynamic programming,接下来看下《Introduction to algorithms》对动态规划的定义:

A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.

翻译过来:

动态规划算法解决每一个子问题,仅一次,然后保存子问题的结果到内存表中,以此来避免对子问题的重复计算。

两种实现方法

  • top-down with memoization 使用内存自顶向下。保存子问题的结果,之后在求解某个子问题时,若其用到的某个子问题且已经保存了结果,直接返回。
  • bottom-up method 在求某个子问题时,会依赖已经求出的更小的子问题的解。

第一种方法符合平常的思维模式,第二种和第一种有点反过来的意思。

03

动态规划好在哪里

在上一推送中,给出了一堆括号,其中某个子字符括号串是无效的,然后要求最长有效串。 动态规划:括号知多少

如果采取穷举的方法,时间复杂度会达到 O(n^2),但是这种方法的空间复杂度却为 O(1) 。

为了降低时间复杂度,采取了动态规划算法,使得时间复杂度降为 O(n),还记得为此付出的代价吗?

是的,空间复杂度达到了O(n),与穷举相比。

因此,动态规划法,通过牺牲空间,换来了时间效率,这称作 time-memory trade-off 。

需要弄明白的是,动态规划通过牺牲空间,是如何获得执行效率的呢?

这个问题便是动态规划的核心所在,它将某个子问题的计算结果保存到这个内存表中,为之后的问题提供服务,以此来提升执行效率。

04

爬楼梯

今天介绍的这个实际问题,是动态规划比较容易理解的实际应用例子之一,请看下面的问题描述:

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? Note: Given n will be a positive integer.

意思是说,每次你可以爬1个或2个台阶,问爬到第 n 个台阶,一共有多少种不同的方法。

例子1:

爬到第2个台阶,共有2种方法,
1. 第一步爬1个,第二步爬1个
2. 第一步爬2个

例子2:

爬到第3个台阶,共有3种方法:
1. 第一步,二步,三步分别爬1个
2. 第一步爬1个,第二步爬2个
3. 第一步爬2个,第二步爬1个

这个问题可以明显分解为一系列子问题,它包括最优解可以被构建,通过子问题的最优解,可以用动态规划解决这个问题。

一个人到达第 i 层楼底包括两种方法:

  1. 选择从第 i-1 层再爬1步到
  2. 选择从第 i-2 层再爬2步到

因此,如果用 dp[i] 表示达到第 i 层楼梯的所有方法,那么它进一步等于到达第 i-1 层楼梯的方法加上到达第 i-2 层楼梯的方法的和,即

dp[i] = dp[i-1] + dp[i-2]

有了这个递推公式,自然代码就好写了,如下所示:

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];
}

06

总结

在爬楼梯这个实际问题中,看到了动态规划的典型特征,用到了O(n)的空间复杂度,记录已经算过的爬到第i-2层和第i-1层的解,然后通过递推公式得到爬到第i层的解。

算法的时间和空间复杂度都为 O(n) 。

原文发布于微信公众号 - 算法channel(alg-channel)

原文发表时间:2017-11-05

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老九学堂

技术大咖分享:如何评价一段代码?

经常有人微信问老九君,什么样的代码才算是好代码。这个问题其实见仁见智,业内也没有统一的标准可以使用。我仔细梳理了一下自己评价代码的方法,总结了五个评价指标。 规...

3676
来自专栏好好学java的技术栈

“365算法每日学计划”:01打卡

如果有小伙伴很少接触到这种题目的话,可能会觉得有点陌生,不知道从何下手,可能一开始我们能想到“最笨”的方法,但是也觉得挺有“娱乐性”的方法。

2813
来自专栏take time, save time

[细节决定B度]之二分搜索也不易啊

     实事求是的说二分搜索是我学习算法的时候学的最好,理解的最透彻,能够当时就写出代码的的算法。事到如今,就如我可以分分钟写出hello world一样,我...

3086
来自专栏阿凯的Excel

乘积求和及符合某个条件的乘积求和

如何得到两个数组的乘积求和呢??案例如下: ? 已知每个地市的销售单价和销售数量,需要知道整个表的销售总金额,怎么做??? 普通青年做法: ? 小编客观公正...

4339
来自专栏程序人生

抽象的能力

人类的智商从低幼逐渐走向成熟的标志之一就是认识和运用数字的能力。当我们三四岁的时候,数数虽然能够熟练地对一百以内的数字随心所欲地倒背如流,但数字对孩童时代的我们...

3457
来自专栏非著名程序员

如何评价一段代码

经常有人微信问我,什么样的代码才算是好代码。这个问题其实见仁见智,业内也没有统一的标准可以使用。我仔细梳理了一下自己评价代码的方法,总结了五个评价指标。 1、规...

1799
来自专栏程序员互动联盟

【专业技术】结构化与面向对象到底啥区别?

存在问题: 什么是面向对象什么是结构化,这个问题一直困惑着很多新手,不容易搞清楚。 解决方案: 1.基本原则的对比: 结构化方法的基本思想就是将待解决的问题看作...

2705
来自专栏逸鹏说道

重温数据结构系列随笔:数据结构的基本概念

现在项目已经踏上正轨,有不少时间可以用来学习,昨晚发现柜子里那本大学时候啃过无数遍的(数据结构 C语言版),那真的无限感叹啊,初恋女友啊,大学回忆啊都涌上心头。...

2914
来自专栏老九学堂

程序员揭秘:火爆朋友圈的左右脑年龄测试,真相只是一个随机函数!

最近,老九的朋友圈已经被左右脑测试刷爆了,老九也去测试了一下,只需要进入相应入口并回答几个设定的问题后,就会出现左右脑两个年龄测试结果。 ? 有不少小伙伴晒出自...

3836
来自专栏我是攻城师

统计学里面的百分位数是什么意思

6175

扫码关注云+社区

领取腾讯云代金券