动 态 规 划
以斐波那契数列 为例:
\(f_i\) 状态
\(f_i = f_{i-1}+f_{i-2}\) 转移方程
\(f_0 = 0\) , \(f_1 = 1\) 初始化
dp的实现方法一般有三种，其中的两种（最重要的）如下
#include<bits/stdc++.h>
using namespace std;
int f[200010];
signed main(){
int n;
scanf("%d",&n);
/*
f[1]=1;
f[0]=0;
for(int i=2;i<=n;i++)
f[i]=f[i-1]+f[i-2];//1.用别人的值去维护自己的值
printf("%d\n",f[n]);
memset(f,0,sizeof(f));
*/
f[1]=1;
f[0]=0;
for(int i=0;i<=n;i++){//2.用自己的值去维护自己的值
f[i+1]+=f[i];
f[i+2]+=f[i];
}
printf("%d",f[n]);
return 0;
}
第三种
#include<bits/stdc++.h>
using namespace std;
int f[200010];//f[i]表示斐波那契数列的第i项
bool g[200010];//g[i]表示斐波那契数列第i项有没有求出来
int n;
int dfs(int n){//求斐波那契数列第i项
if(n==0)return 0;
if(n==1)return 1;
if(g[n])return f[n];
g[n]=true;
f[n]=dfs(n-1)+dfs(n-2);//记忆化搜索
return f[n];
}
signed main(){
scanf("%d",&n);
printf("%d",dfs(n));
return 0;
}
最大上升子序列(化身P党)：
uses math;
var f:array[0..5005] of longint;
var a:array[0..5005] of longint;
var n,i,j,ans:longint;
begin
readln(n);
for i:=1 to n do begin
read(a[i]);
end;
f[1]:=1;
for i:=2 to n do begin
for j:=1 to i-1 do begin
if a[j]<a[i] then begin
f[i]:=max(f[i],f[j]);
end;
end;
f[i]:=f[i]+1;
end;
ans:=0;
for i:=1 to n do begin
ans:=max(f[i],ans);
end;
writeln(ans);
end.