百度百科↓
动态规划 (dynamic programming) 是运筹学的一个分支, 是求解决策过程 (decision process) 最优化的数学方法. 20 世纪 50 年代初美国数学家 R.E.Bellman 等人在研究多阶段决策过程 (multistep decision process) 的优化问题时, 提出了著名的最优化原理(principle of optimality), 把多阶段过程转化为一系列单阶段问题, 利用各阶段之间的关系, 逐个求解, 创立了解决这类过程优化问题的新方法 -- 动态规划. 1957 年出版了他的名著《Dynamic Programming》, 这是该领域的第一本著作.
T1 http://topoi.top/contests/view/1316/0
DP 例题
转移方程:
- DP[i][j]=Max(DP[i-1][j],DP[i-1][j-1])+a[i][j]
- ans=Max(DP[n][1..n])
- #include <bits/stdc++.h>
- #define Max(a,b) a>b?a:b
- using namespace std;
- typedef long long LL;
- inline LL read() { LL x=0; int f=1; char ch=getchar();
- while(!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar();}
- while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x*f;
- }
- int n;
- const int N=1<<7;
- LL a[N][N];
- LL DP[N][N];
- signed main(){
- n=read();
- for(register int i=1;i<=n;i++)
- for(register int j=1;j<=i;j++) a[i][j]=read();
- for(register int i=1;i<=n;i++)
- for(register int j=1;j<=i;j++) DP[i][j]=a[i][j],DP[i][j]+=Max(DP[i-1][j],DP[i-1][j-1]);
- LL ans=-1;
- for(register int i=1;i<=n;i++) ans=Max(ans,DP[n][i]);
- cout << ans << endl ;
- return 0;
- }
- T2
来源: http://www.bubuko.com/infodetail-2966096.html