解释这一动态规划爬正台阶code [英] Explain this dynamic programming climbing n-stair code

问题描述

但问题是

你攀登楼梯的情况下，每次可以使1级或2级的楼梯有n个步骤。在有多少不同的方式你能爬上楼梯？

"You are climbing a stair case. Each time you can either make 1 step or 2 steps. The staircase has n steps. In how many distinct ways can you climb the staircase?"

以下是此问题的code解决方案，但我无法理解它。任何人都可以解释我

Following is the code solution for this problem but I am having trouble understanding it. Can anybody explain me

int stairs(int n) {
  if (n == 0) return 0;
  int a = 1;
  int b = 1;
  for (int i = 1; i < n; i++) {
    int c = a;
    a = b;
    b += c;
  }
  return b;
 }

谢谢

推荐答案

嗯，首先你需要了解递推公式，以及如何从中获得迭代之一。

Well, first you need to understand the recursive formula, and how we derived the iterative one from it.

的递推公式是：

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

（ F（N-1）的一步， F（N-2）的两个步骤，总人数是如何使用这些选项中的一个数字。 - 这样的总和）

(f(n-1) for one step, f(n-2) for two steps, and the total numbers is the number of ways to use one of these options - thus the summation).

如果你仔细观察 - 这也是一个众所周知的系列 - 斐波那契数和解决的方法就是计算每个数字BUTTOM行动，而不是重新计算一次递归遍地，从而更有效的解决方案。

If you look carefully - this is also a well known series - the fibonacci numbers, and the solution is simply calculating each number buttom-up instead of re-calculating the recursion over and over again, resulting in much more efficient solution.

这篇关于解释这一动态规划爬正台阶code的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！