第一次遇见动态规划

一、什么是动态规划

动态规划是对问题的各状态维度进行分阶段、有顺序、无重复、决策性的遍历求解的算法思想。

“状态”、“阶段”、“决策”是构成动态规划算法的三要素。

问题能用动态规划求解需要满足三个基本条件：

1、子问题重叠性：动态规划算法是把原问题视作若干个重叠子问题的逐层递进，每个子问题的求解过程都构成一个“阶段”。在完成前一个阶段的计算后，动态规划才会执行下一阶段的计算。

2、无后效性：动态规划算法要求已经求解的子问题不受后续阶段的影响。

3、最优子结构性质：动态规划是用来求解最优化问题。所以下一阶段的最优解应该能够由前面各阶段子问题的最优解导出。（类似于贪心策略）

在求解过程中我们如果能将问题形式化为状态空间，进一步抽象出其“状态转移方程DP”,问题就得到了极大的解决。

以下以例题的形式向读者展现动态规划的思想在实战中的应用，请读者自行思考其韵味。

二、线性DP

1、数字三角形

​

#include <iostream> using namespace std; const int N=105; int a[N][N]; int dp[N][N];//dp[i][j]表示走到（i，j）时的总和 int main() { int n;cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) dp[i][j]=a[i][j]+max(dp[i-1][j-1],dp[i-1][j]); //点（i，j）是从上一步（i-1，j-1）或（i-1，j）选取最优的策略，即值最大走到的 if(n&1) cout<<dp[n][n/2+1]; else cout<<max(dp[n][n/2],dp[n][n/2+1]);//最后肯定是走到最后一行的中间 return 0; }

2.最长上升子序列（LIS）

#include <iostream> using namespace std; const int N=1e3+5; int a[N]; int dp[N];//dp[i]表示以a[i]结尾的，比a[i]小的最多有几个a[j](j<=i) int main() { int n,ans;cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { dp[i]=1; for(int j=1;j<=i;j++) { if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1); //对于每个以a[i]结尾的dp[i]，依次遍历dp[j](j<=i),寻找符合条件的 } ans=max(ans,dp[i]); } cout<<ans; return 0; }

3.最长公共子序列（LCS）

#include <iostream> using namespace std; const int N=1e3+9; int a[N],b[N]; int dp[N][N];//dp[i][j]表示a[1~i]序列和b[1~j]序列中的最长公共子序列的长度 int main() { int n,m;cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int j=1;j<=m;j++) cin>>b[j]; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1; //当a[i]==b[j]时，可以将他们作为公共元素插入到LCS的后面，使得长度变长1 else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);//这已经包含了dp[i-1][j-1] //当a[i]！=b[j]时，说明此时LCS不会延长，那就从dp[i-1][j]和dp[i][j-1]中取大的作为最长的元素 } } cout<<dp[n][m]; return 0; }

通过这三个基本例题，相信大家已经能够明白用动态规划求解问题的三个基本条件

三、背包

请期待…………