题解 | #BC166 小乐乐走台阶#

题解 | #BC166 小乐乐走台阶#

两种解法

• 第一种解法：递归
• 第二种解法：动态规划

（1）递归解法

要求到达第n阶台阶的走法，则我们可以首先计算第n-1阶和第n-2阶的走法，然后将n-1和n-2的走法相加，就可以得到n阶的走法。
依次类推，直到计算到第1阶即可结束，n=1时候，此时只有一种解法。
所以可以采用递归的方式，依次从n计算n-1和n-2阶的走法。

具体实现代码：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int sum = stairs(n);
        System.out.println(sum);
    }
    public static int stairs(int n) {
        // 递归结束条件
        if (n <= 1) {
            return 1;
        }
        // 递归逻辑
        return stairs(n - 1) + stairs(n - 2);
    }
}

（2）动态规划

动态规划，这种做法其实是为了解决递归过程走重复计算的问题。
我们可以看到，每次递归计算的时候，都会出现重复计算的问题，例如：
1、计算n阶的时候，需要计算n-1和n-2两个走法。
2、计算n-1阶的时候，需要计算n-2和n-3两个走法。
可以看到，上面两个都计算了n-2的结果。
为了避免重复计算，我们可以在计算过程中，将已经计算的保存起来，然后下次需要的时候，直接获取计算结果就可以啦，而不用重复的计算，从而提高了运行效率。
但是，这种方式是采用空间换取时间的方式，因为需要保存计算结果，所以需要额外的内存空间来存储数据。

动态转移方程

// 这里，dp[i]代表：到达第i个台阶有几种走法
dp[i] = dp[i-1] + dp[i-2];

具体实现代码：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        // 动态规划
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        // 开始计算
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        System.out.println(dp[n]);
    }
}