动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。
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; }
原文：https://www.cnblogs.com/qf-breeze/p/10425715.html