Java 动态规划“爬楼梯”，不懂逻辑

Question

问题是：你正在爬楼梯。到达顶部需要 n 步。每次您可以爬 1 或 2 个台阶。您可以通过多少种不同的方式登顶？

而且我看到一个java代码是正确的，但是我不明白其中的逻辑。谁能给我解释一下？ a,b,c是什么意思？

public int climbStairs(int n) {

    if (n<2) return 1;

    int a = 1;
    int b = 1;
    int c = 1;

    for (int i=2; i<=n; i++){
        c = b;
        b = a + b;
        a = c;
    }
    return b;
}

Answer 1

递推公式为

f(n) = f(n-1) + f(n-2)
f(0) = f(1) = 1

在代码中翻译成a, b, c

if (n<2) return 1;

int a = 1;
int b = 1;
int c = 1;

上面定义了 f(0) = f(1) = 1，下面为 n >= 2

计算了 f(n) = f(n-1) + f(n-2)

for (int i=2; i<=n; i++){
    c = b;     // f(i-1) is temporary saved in c
    b = a + b; // f(i-2) + f(i-1) is saved in b
    a = c;     // f(i-1) is saved in a for the next iteration
}

Answer 2

代码本身基本上是一个斐波那契数生成器。

int a = 1;
int b = 1;
int c = 1;

for (int i=2; i<=n; i++){
    c = b;
    b = a + b;
    a = c;
}

创建第 n 个斐波那契数，从 1 开始代表 n = 0。

所以更重要的问题是：
可能的方式数如何对应斐波那契数列？

对于 n = 0 和 n = 1，答案很简单：只有一种方法：不要移动 (0)，迈出一步 (1)。对于任何其他 n，我们可以使用递归方法：有两种方法可以到达步骤 n：从 n - 1 走一小步或从 n - 2 走一大步。这与斐波那契数列相同：fib(n + 2) = fib(n + 1) + fib(n).

Java 动态规划“爬楼梯”，不懂逻辑

Java dynamic programming “Climbing Stairs”, do not understand the logic

java

algorithm

dynamic-programming

fibonacci