首页 > 代码库 > 动态规划走楼梯问题

动态规划走楼梯问题

有一条楼梯,总共有9级阶梯,从地面上出发,如果每次可以走3级,4级或6级楼梯,问共有几种方案可以走到?

解决方案一:

第一个方法比较简单,很容易想到,就是用深度搜索,我们可以反过来,把情况看出从第9层阶梯走到路面,把所有可以出现的情况都列出来,然后判断是否能到达第9级阶梯,如果可以,就把方案数加一。

代码如下:

public class DPStair {
    
    static int count=0; //计算F(n)被调用了计次
    static int F(int n)
    {
        count++;
        if(n==0) return 1;         //n等于0,恰好到达9层阶梯
        if(n<0) return 0;                        
        return F(n-3)+F(n-4)+F(n-6);  //深搜,走3级,4级,6级能到达目的地的次数相加
    }
    
    public static void main(String[] args) {
        int n=9;
        System.out.println(F(n)+" count="+count);
    }
}

但如果现在要求得是能到底第90级阶梯的次数呢,我用上面深搜的方法,程序大概运行了一分钟左右才得出结果,这才求90级阶梯,速度太慢了。下面用动态规划优化下这个程序。

我们把这个问题分解下,走到第9级楼梯的方案可以看出从第8级楼梯走到第9级楼梯的方案加上第7级楼梯走到第9级楼梯的方案······

走到第8级楼梯的方案可以看出从第7级楼梯走到第8级楼梯的方案加上第6级楼梯走到第8级楼梯的方案······

这样类推下来,我们可以看到,用上面的深搜方法,仔细观察下,计算第第7级楼梯走到第8级楼梯的方案 和 计算第第7级楼梯走到第9级楼梯的方案 这两次计算的重复了,也就是说我们重复计算了两次走到第7级楼梯的方案,所以我们考虑下把走到某一级楼梯的方案数记录下来,如果再次需要用到走到该级楼梯方案数的时候,就不需要再去计算,把之前记录下来的方案数取出来用就行了,代码如下:

public class Stairs {
    static int count=0;
    static int[] Sum;     //用来记录走到某级楼梯的方案数
    static int F(int n)
    {
        count++;
        if(n==0) return 1;
        if(n<0) return 0;        
        if(Sum[n]!=-1) return Sum[n];     //如果走到该级楼梯的方案数已经存在,直接取用就行,不用继续深搜计算走到该级楼梯的方案数            
        Sum[n]=F(n-3)+F(n-4)+F(n-6); //如果没有记录,计算能走到该级楼梯的方案数
        return Sum[n];   //返回方案数
    }
    
    public static void main(String[] args) {
        int n=90;
        Sum=new int[n+1];
        for(int i=0;i<=n;i++) Sum[i]=-1;   //初始化-1,表示走到该级楼梯的方案数还没有记录
        System.out.println(F(n)+" count="+count);
    }

}

但n=90的时候,我们运行程序,结果是秒出的,输出count的值是262,而用上面那个没有优化深搜的程序,count输出是负数,也就是已经超出了Int的最大值范围,可以比较出来优化的效果还是比较明显的

动态规划走楼梯问题