第一次遇见动态规划

一、什么是动态规划动态规划是对问题的各状态维度进行分阶段、有顺序、无重复、决策性的遍历求解的算法思想。“状态”、“阶段”、“决策”是构成动态规划算法的三要素。问题能用动态规划求解需要满足三个基本条件1、子问题重叠性动态规划算法是把原问题视作若干个重叠子问题的逐层递进每个子问题的求解过程都构成一个“阶段”。在完成前一个阶段的计算后动态规划才会执行下一阶段的计算。2、无后效性动态规划算法要求已经求解的子问题不受后续阶段的影响。3、最优子结构性质动态规划是用来求解最优化问题。所以下一阶段的最优解应该能够由前面各阶段子问题的最优解导出。类似于贪心策略在求解过程中我们如果能将问题形式化为状态空间进一步抽象出其“状态转移方程DP”,问题就得到了极大的解决。以下以例题的形式向读者展现动态规划的思想在实战中的应用请读者自行思考其韵味。二、线性DP1、数字三角形​#include iostream using namespace std; const int N105; int a[N][N]; int dp[N][N];//dp[i][j]表示走到ij时的总和 int main() { int n;cinn; for(int i1;in;i) for(int j1;ji;j) cina[i][j]; for(int i1;in;i) for(int j1;ji;j) dp[i][j]a[i][j]max(dp[i-1][j-1],dp[i-1][j]); //点ij是从上一步i-1j-1或i-1j选取最优的策略即值最大走到的 if(n1) coutdp[n][n/21]; else coutmax(dp[n][n/2],dp[n][n/21]);//最后肯定是走到最后一行的中间 return 0; }2.最长上升子序列LIS#include iostream using namespace std; const int N1e35; int a[N]; int dp[N];//dp[i]表示以a[i]结尾的比a[i]小的最多有几个a[j](ji) int main() { int n,ans;cinn; for(int i1;in;i) cina[i]; for(int i1;in;i) { dp[i]1; for(int j1;ji;j) { if(a[i]a[j]) dp[i]max(dp[i],dp[j]1); //对于每个以a[i]结尾的dp[i]依次遍历dp[j](ji),寻找符合条件的 } ansmax(ans,dp[i]); } coutans; return 0; }3.最长公共子序列LCS#include iostream using namespace std; const int N1e39; int a[N],b[N]; int dp[N][N];//dp[i][j]表示a[1~i]序列和b[1~j]序列中的最长公共子序列的长度 int main() { int n,m;cinnm; for(int i1;in;i) cina[i]; for(int j1;jm;j) cinb[j]; for(int i1;in;i) { for(int j1;jm;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]中取大的作为最长的元素 } } coutdp[n][m]; return 0; }通过这三个基本例题相信大家已经能够明白用动态规划求解问题的三个基本条件三、背包请期待…………