动态规划-楼梯问题

enali 发布于2019-08-16 16:07 / 1352人阅读

摘要：程序实现首先用递归进行实现，与动态规划做比较。递归动态规划从底到上推导，，每次迭代，只保留之前的两个状态，即可推导新的状态。

1、问题描述

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

输入输出描述
Input
输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。
Output
对于每个测试实例，请输出不同走法的数量
示例：

Sample Input
2
2
3
Sample Output
1
2

2、思路分析

利用动态规划（DP，dynamic programming）思想，简单来说：大事化小小事化了

假设10级，考虑只差最后一步到10级，一步走1阶或2阶，只有两种可能：到9阶和到8阶。
如果到9阶的走法有X种，到8阶的走法有Y种，那么，总走法=X+Y。
即：F(10)=F(9)+F(8)
同理，F(9)=F(8)+F(7)，F(8)=F(7)+F(6)，这样问题可以从10阶到 [9和8] 阶，再到 [9和8] 拆开的阶，这样往下，分阶段将问题简化。

寻找基准或者初始解：当为F(2)和F(1)时，前者有两种走法（1+1，2），后者有一种走法（1）。
即：①F(2)=2，F(1)=1。再加上②F(10)=F(9)+F(8)，

得到三个动态规划的概念：
【最优子结构】：F(9)和F(8)，是F(10)的最优子结构
【边界】：F(1)和F(2)是问题的边界，无法再简化/拆解
【状态转移方程】：F(10)=F(9)+F(8)，上下阶段的关系

递归公式：F(n)=F(n-1)+F(n-2)，实为斐波那契数列的递归公式。

3、程序实现

首先用递归进行实现，与动态规划做比较。前者代码简洁，但执行效率不如后者。

1）递归

int getWays(int n){
    if(n<1) return 0;
    if(n==1) return 1;
    if(n==2) return 2;
    return getWays(n-1)+getWays(n-2)
}

2）动态规划

从底到上推导：
F(1)=1，F(2)=2，
F(3)=F(2)+F(1)=1+2
F(4)=F(3)+F(2)=3+2
每次迭代，只保留之前的两个状态，即可推导新的状态。

源程序：

import java.util.Scanner;

/**
 * Input:输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。
 * Output:对于每个测试实例，请输出不同走法的数量
 */
public class DPSumsung {

    public static int getWays(int n) {
        if(n<1) return 0;
        if(n==1) return 1;
        if(n==2) return 2;
        
        int a=1;
        int b=2;
        int next=0;
        for(int i=3;i<=n;i++) {
            next=a+b;
            a=b;
            b=next;
        }
        return next;
    }
    
    public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);
        int count=sc.nextInt();
        int[] ways=new int[count];
        int i=0;
        int n=sc.nextInt();
        while(n>=1&&n<=40) {         
            ways[i++]=DPSumsung.getWays(n);
            if(i>=count)
                break;
            n=sc.nextInt();
        }
        for(int temp:ways) {
            System.out.println(temp);
        }
        sc.close();
    }
}

4、算法分析

时间复杂度为O(N)，空间复杂度为O(1)。

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

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

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

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

摘要：动态规划算法通常基于一个递推公式及一个或多个初始状态。动态规划有三个核心元素最优子结构边界状态转移方程我们来看一到题目题目有一座高度是级台阶的楼梯，从下往上走，每跨一步只能向上级或者级台阶。概念动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。动态规划算法通常基于一个递推公式及一个或多个初始状态...

cyixlq 2019-08-23 10:52 评论0 收藏0
看动画轻松理解「递归」与「动态规划」

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

cnio 2019-07-30 18:41 评论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