首先，什么是动态规划？

　　动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。其实就是分解问题，分而治之。可能这样说大家都不太理解，其实这个有点类似于数学中的递推公式。来举一个简单的例子，看下边这个题：

N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。

这就是动态规划最简单的一个列子。拿到这个题，大家是不是都有点迷，这个到底怎么做？

是不是没有思路，那么按照动态规划思想，我们可以先分析下问题，每次都有两种跳法，分别是一阶或者两阶，那么如果当前是第n个台阶，那么跳法是不是是(n-1)台阶的跳法数加上(n-2)台阶的跳法数？

如果划算成公式是F(n) =  F(n-1)+F(n-2)。

F(n)代表第n阶台阶的跳法的数量。这不就相当于找到了一个递推公式，然后来进行计算。

N阶楼梯上楼问题
题目描述：
N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。（要求采用非递归）
输入描述：
输入包括一个整数N,(1<=N<90)。
输出描述：
可能有多组测试数据，对于每组数据，
输出当楼梯阶数是N时的上楼方式个数。
输入样例#:
4
输出样例#:
5
题目来源：
DreamJudge 1413

题目解析：根据上面的分析得出公式F(n) =  F(n-1)+F(n-2)，然后递推即可。

参考代码

#include <stdio.h>  
  
int main() {  
    int i,N;  
    long long a[90];  
    while(scanf("%d",&N) != EOF) {  
        a[1]=1;  
        a[2]=2;  
        for(i=3;i<=N;i++)  
            a[i]=a[i-1]+a[i-2];  
        printf("%lld\n",a[N]);  
    }  
    return 0;  
}  

练习题目

DreamJudge 1197 吃糖果
DreamJudge 1033 细菌的繁殖