动态规划入门（以爬楼梯为例）

cyixlq 发布于2019-08-23 10:52 / 861人阅读

摘要：动态规划算法通常基于一个递推公式及一个或多个初始状态。动态规划有三个核心元素最优子结构边界状态转移方程我们来看一到题目题目有一座高度是级台阶的楼梯，从下往上走，每跨一步只能向上级或者级台阶。

概念

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。

基本思想

要解决一个给定的问题，我们需要解决其不同部分（即解决子问题），再合并子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图只解决每个子问题一次，从而减少计算量。
一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。
这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
动态规划有三个核心元素：
1.最优子结构
2.边界
3.状态转移方程

我们来看一到题目

题目

有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。求出一共有多少种走法。

比如，每次走1级台阶，一共走10步，这是其中一种走法。
再比如，每次走2级台阶，一共走5步，这是另一种走法。

但是这样一个个算太麻烦了，我们可以只去思考最后一步怎么走，如下图

这样走到第十个楼梯的走法 = 走到第八个楼梯 + 走到第九个楼梯
我们用f(n)来表示走到第n个楼梯的走法，所以就有了f(10) = f(9) + f(8)
然后f(9) = f(8) + f(7), f(8) = f(7) + f(6)......

这样我们就得出来一个递归式：
f(n) = f(n-1) + f(n-2);
还有两个初始状态：
f(1) = 1;
f(2) = 2;

这样就得出了第一种解法

方法一：递归求解

function getWays(n) {

    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    return getWays(n-1) + getWays(n-2); 
}

这种方法的时间复杂度为O(2^n)

可以看到这是一颗二叉树，数的节点个数就是我们递归方程需要计算的次数，
数的高度为N，节点个数近似于2^n
所以时间复杂度近似于O(2^n)

但是这种方法能不能优化呢？
我们会发现有些值被重复计算，如下图

相同颜色代表着重复的部分，那么我们可不可以把这些重复计算的值记录下来呢？
这样的优化就有了第二种方法

方法二：备忘录算法

const map = new Map(); 
function getWays(n) {

    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    if (map.has(n)) {
        return map.get(n);
    }
    const value = getWays(n-1) + getWays(n-2);
    map.set(n, value);
    return value; 
}

因为map里最终会存放n-2个键值对，所以空间复杂度为O(n),时间复杂度也为O(n)

继续想一想这就是最优的解决方案了吗？

我们回到一开始的思路，我们是假定前面的楼梯已经走完，只考虑最后一步，所以才得出来f(n) = f(n-1) + f(n-2)的递归式，这是一个置顶向下求解的式子
一般来说，按照正常的思路应该是一步一步往上走，应该是自底向上去求解才比较符合正常人的思维，我们来看看行不行的通

这是一开始走的一个和两个楼梯的走法数,即之前说的初始状态

这是进行了一次迭代得出了3个楼梯的走法，f(3)只依赖于f(1) 和 f(2)

继续看下一步

这里又进行了一次迭代得出了4个楼梯的走法，f(4)只依赖于f(2) 和 f(3)

我们发现每次迭代只需要前两次迭代的数据，不用像备忘录一样去保存所有子状态的数据

方法三：动态规划求解

function getWays(n) {

    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    // a保存倒数第二个子状态数据，b保存倒数第一个子状态数据， temp 保存当前状态的数据
    let a = 1, b = 2;
    let temp = a + b;
    for (let i = 3; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp; 
    }
    return temp; 
}

这是我们可以再看看当前的时间复杂度和空间复杂度
当前时间复杂度仍为O(n)，但空间复杂度降为O(1)
这就是理想的结果

总结

这只是动态规划里最简单的题目之一，因为它只有一个变化维度
当变化维度变成两个、三个甚至更多时，会更加复杂，背包问题就是比较典型的多维度问题，有兴趣的可以去网上看看《背包九讲》

GPU云服务器云服务器动态规划动态规划python java动态规划代码 java零钱动态规划

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96772.html

看动画轻松理解「递归」与「动态规划」

摘要：程序员小吴打算使用动画的形式来帮助理解递归，然后通过递归的概念延伸至理解动态规划算法思想。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。难点就在于找出动态规划中的这三个概念。在学习「数据结构和算法」的过程中，因为人习惯了平铺直叙的思维方式，所以「递归」与「动态规划」这种带循环概念（绕来绕去）的往往是相对比较难以理解的两个抽象知识点。...

cnio 2019-07-30 18:41 评论0 收藏0
动态规划-楼梯问题

摘要：程序实现首先用递归进行实现，与动态规划做比较。递归动态规划从底到上推导，，每次迭代，只保留之前的两个状态，即可推导新的状态。 1、问题描述有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？输入输出描述Input输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1

enali 2019-08-16 16:07 评论0 收藏0
LeetCode 之 JavaScript 解答第70题 —— 爬楼梯（Climbing Stair

摘要：小鹿题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。算法思路二种解决思路，第一利用递归第二利用动态规划。就是因为有了重复元素的计算，导致了时间复杂度成指数的增长。 Time：2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿题目：Climbing Stairs You a...

chemzqm 2019-08-23 16:55 评论0 收藏0
70-爬楼梯

摘要：前言最近在练习动态规划的题目，然后就随便选择了一道简单的题目爬楼梯，题目如下假设你正在爬楼梯。斐波那契数列爬楼梯实现代码爬楼梯前言最近在练习动态规划的题目，然后就随便选择了一道简单的题目——爬楼梯，题目如下：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入： 2 ...

CompileYouth 2019-08-19 11:05 评论0 收藏0
每日一道算法题--leetcode 746--使用最小花费爬楼梯--python

摘要：代码思路最简单的一维动态规划问题，自底向上。上代码看效果，时间复杂度线性级别这里有一个动态规划系列题目整理，供大家参考【题目描述】 showImg(https://user-gold-cdn.xitu.io/2019/5/27/16af88f6f38f5da3); ！！题干里的示例1需要仔细看一下哦，要到达顶层，即20那一层，可以跳过20这一层达到更高一层，也因此我们给cost数组最后加一个...

Euphoria 2019-05-27 17:41 评论0 收藏0