demo

#include<bits/stdc++.h>  //斐波那契数列 
using namespace std;

const int N = 1e6 + 10;
int dp[N]; 
int f(int n)
{
	if (dp[n] != 0) return dp[n]; //记忆化 
	if (n < 3) return dp[n] = 1 % 1000;
	else return dp[n] = (f(n-1) + f(n-2)) % 1000;
}
int main()
{
	int n;
	cin >> n;
	cout << f(n);
	return 0;
}

动态规划dp 

斐波那契数列 
fn = f(n-1) + f(n-2)
思想： 把中间状态的值记录下来。 

解题步骤
1.设状态 
dp[i][j]表示从a[1][1]到a[i][j]的最优路径（路径上的数字和的最大值）
2.找状态转移方程（规律）
a                         dp 
7                         7 
3 8                       10 15 
8 1 0                     18 16 15    
2 7 4 4                   20 25 20 19     
4 5 2 6 5                 24 30 27 26 24      
 
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]
3.写代码