动态规划-斐波那契数列

也可以压缩不用dp数组，关键在于找规律，思路来源http://t.csdnimg.cn/Y81XV

#include <iostream>
#include <vector>
using namespace std;
/*
n=1 , 1
n=2 , 2
n=3 , 3
n=4 , 5
发现规律：f(n)=f(n-1)+f(n-2)  也可以从排放形状入手
带入知道，f(6)=13
*/
int main(){
    int n;
    cin >> n;  // 读取n值
    if(n <= 2){
        // 直接返回n，因为当n为1或2时，结果分别为1和2
        cout << n;
        return 0;
    }
    // 初始化dp数组，其中dp[i]存储第i个数的值
    vector<int> dp(n+1);
    dp[1] = 1;  // f(1) = 1
    dp[2] = 2;  // f(2) = 2
    // 从第3个数开始，每个数都是前两个数的和
    for(int i = 3; i <= n; i++){
        dp[i] = (dp[i-1] + dp[i-2]) % 999983;  // 使用模运算防止溢出
    }
    // 输出第n个数的值
    cout << dp[n];
    return 0;
}