202052 - 序号6 - （4399 - 2020年）

（java实现）

题目描述：

段誉身具凌波微波，动无常则，若危若安，一次能走一级台阶或者两级台阶，他要爬一段30级的山路，问有多少种走法？分析如何计算，然后编程解答。
进阶问题：当他轻功熟练度提升，一次最多可以走三级，那就结果有什么变化？后来走火入魔了，不能走一级，只能走二或三级，又有什么变化？

输入描述：

输入一个数n（1<=n<=30），代表段誉要爬一段n级的山路。

输出描述：

输出三个整数a,b,c（以空格相间）。其中a为段誉一次能走一级或两级台阶的走法；b为段誉一次能走一级、二级或三级台阶的走法；c为段誉一次能走二级或三级台阶的走法。

示例1：

输入

3

输出

3 4 1

问题分析：

通过分析，可以得出如下规律
第一种情况：dp[i] = dp[i-1] + dp[i-2];
第二种情况：dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
第三种情况：dp[i] = dp[i-2] + dp[i-3];
思路一：使用递归实现；
思路二：使用非递归实现

参考代码：

思路一实现：

import java.util.*;
public class Main {

    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int a=0, b=0, c=0;
        int t1=0,t2=1;
        int tmp = 0;
        //a
        for (int i=0; i<n; i++)
        {
            a = t1 +t2;
            t1 = t2;
            t2 = a;
        }
        //b
        b = getB(n);
        c = getC(n);
        System.out.println(a+" "+b+" "+c);
    }
    public static int getA(int n)
    {
        if (n < 0)
            return 0;
        else if (0 == n)
            return 1;
        return getA(n-1)+getA(n-2);
    }
    public static int getB(int n)
    {
        if (n < 0)
            return 0;
        else if (0 == n)
            return 1;
        return getB(n-1)+getB(n-2)+getB(n-3);
    }
    public static int getC(int n)
    {
        if (n < 0)
            return 0;
        else if (0 == n)
            return 1;
        return getC(n-2)+getC(n-3);
    }
}

思路二实现：

import java.util.*;
public class Main {

    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] dp1 = new int[31];
        int[] dp2 = new int[31];
        int[] dp3 = new int[31];
        //第一种
        dp1[0] = 1;
        dp1[1] = 1;
        for (int i=2; i<=n; i++)
        {
            dp1[i] = dp1[i-1] + dp1[i-2];
        }
        //第二种
        dp2[0] = 1;
        dp2[1] = 1;
        dp2[2] = 2;
        for (int i=3; i<=n; i++)
        {
            dp2[i] = dp2[i-1] + dp2[i-2] + dp2[i-3];
        }
        //第三种
        dp3[0] = 0;
        dp3[1] = 0;
        dp3[2] = 1;
        dp3[3] = 1;
        for (int i=4; i<=n; i++)
        {
            dp3[i] = dp3[i-2] + dp3[i-3];
        }
        System.out.println(dp1[n]+" "+dp2[n]+" "+dp3[n]);
    }
}