解题思路

这是一个斐波那契数列变种问题。关键点：

  1. 递推关系：

    • 到达第 级的方法 = 从 级跨1步 + 从 级跨2步

  2. 数组存储：

    • 直接初始化数组的前三个值：[0,1,2]
    • 从第四个值开始递推计算

  3. 取模运算：

    • 每次计算时都进行取模，防止溢出

代码

class GoUpstairs {
public:
    int countWays(int n) {
        vector<int> d(n);
        d[0] = 0;
        d[1] = 1;
        d[2] = 2;
        for(int i = 3; i < n; i++) {
            d[i] = (d[i-1] % 1000000007 + d[i-2] % 1000000007) % 1000000007;
        }
        return d[n-1];
    }
};

import java.util.*;
public class GoUpstairs {
    public int countWays(int n) {
        // write code here
        int[] d = new int[n];
        d[0] = 0;
        d[1] = 1;
        d[2] = 2;
        for(int i = 3; i < n; i++) {
            d[i] = (int)(((long)d[i-1] % 1000000007 + d[i-2] % 1000000007) % 1000000007);
        }
        return d[n-1];
    }
}

# -*- coding:utf-8 -*-

class GoUpstairs:
    def countWays(self, n):
        d = [0] * n
        d[0] = 0
        d[1] = 1
        d[2] = 2
        for i in xrange(3, n):
            d[i] = (d[i-1] % 1000000007 + d[i-2] % 1000000007) % 1000000007
        return d[n-1]

算法及复杂度

  • 算法：动态规划（使用数组存储）
  • 时间复杂度：，需要遍历到第 项
  • 空间复杂度：，需要数组存储所有中间结果