#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.写代码