【常见笔试面试算法题12续集一】动态规划算法案例1台阶问题练习题

加qq1126137994 一起学习更多技术！！！

以下问题，都可以用非动态规划的方法做，我为了整理动态规划的方法思路，就全部用动态规划的思路来解决问题，这样还可以简化问题的处理，是时间复杂度更低！！！

动态规划的核心思想，就是化简问题，将整个问题，分解，从最简单的问题开始计算，慢慢累加，最终，便可以达到求得整体问题的答案，这期间，是需要另外开辟空间的，所以说，动态规划，是以空间，换时间的解决方法！！！

案例一：台阶问题练习题

有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法。为了防止溢出，请将结果Mod 1000000007

给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100000。

测试样例：
1
返回：1

这道题比较简单，我们从最简单的问题入手，如果台阶为n级，那么可以分为下面n种情况：
爬到1级台阶：1种方法
爬到2级台阶：2种方法：从2-1=1级开始爬或者从2-2=0级开始爬
爬到3级台阶：3种方法：从3-1=2级开始爬（但是爬到2级是2种方法），或者从3-2=1级开始爬（爬到1级是1种方法），2+1=3；
…
…
爬到n级台阶：f[n-1]+f[n-2]种方法，而这f[n-1]与f[n-2]是前面求过了的，到这里，可直接计算

上面的过程，可简化为一个一维矩阵dp[n],爬到n级台阶需要的方法数。如下图：

代码如下：

class GoUpstairs {
public:
    int countWays(int n) {
        // write code here
        if(n<=2)
            return n;
        int res[n+1];
        res[1]=1;
        res[2]=2;
        for(int i=3;i<n+1;i++)
        {
            res[i]=(res[i-1]+res[i-2])%1000000007;
        }
        return res[n];

    }
};

（注意：上题还可以用递归方法做，但是时间复杂度就会高一些，动态规划就是由递归方法优化而来的）