加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];

    }
};

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