教你彻底学会动态规划——入门篇


  2. #include <iostream>  
  3. #include <algorithm> 
  4. using namespace std; 
  6. #define MAX 101  
  8. int D[MAX][MAX];  
  9. int n; 
  10. int * maxSum; 
  12. int main(){    
  13.     int i,j;    
  14.     cin >> n;    
  15.     for(i=1;i<=n;i++)   
  16.         for(j=1;j<=i;j++)        
  17.             cin >> D[i][j];   
  18.     maxSum = D[n]; //maxSum指向第n行    
  19.     for( int i = n-1; i>= 1;  --i )     
  20.         for( int j = 1; j <= i; ++j )       
  21.             maxSum[j] = max(maxSum[j],maxSum[j+1]) + D[i][j];    
  22.     cout << maxSum[1] << endl;  
  23. }
  • 以上代码中的简化递归算法，即第一次获取到n-1行的所有maxSum值，共n-1个
  • 第二次获取到n-2行的所有maxSum值，共n-2个，这个n-2个值将替换上一次循环产生的的前n-2个值…
  • 最后一次循环时，将只替换一个值，即maxSum数组的第一个值

教你彻底学会动态规划——进阶篇

动态规划的本质，是对问题状态的定义和状态转移方程的定义
动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

  • 每个阶段只有一个状态 -> 递推；
  • 每个阶段的最优状态都是由上一个阶段的最优状态得到的 -> 贪心；
  • 每个阶段的最优状态是由之前所有阶段的状态的组合得到的 -> 搜索；
  • 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到, 而不管之前这个状态是如何得到的 -> 动态规划。
  1. 能用动规解决的问题的特点:
  2. 1) 问题具有最优子结构性质。如果问题的最优解所包含的 子问题的解也是最优的，我们就称该问题具有最优子结 构性质。
  3. 2) 无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。
  5. 即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

虽然我们通常会用递归的方法区分析动态规划的问题，但是最终都会基于循环去编码

动态规划 - 图1

dp基本算法记录

  • 最长公共子串 Longest Common Substring(要求连续)

    1. if ( s1[i-1] == s2[j-1] ) //s1的最左边字符是s1[0]   
    2.   MaxLen(i,j) = MaxLen(i-1,j-1) + 1; 
    3. else  
    4.   MaxLen(i,j) = 0;

  • 最长公共子序列 Longest Common Subsequence(不要求连续)

    1. if ( s1[i-1] == s2[j-1] ) //s1的最左边字符是s1[0]   
    2.   MaxLen(i,j) = MaxLen(i-1,j-1) + 1; 
    3. else  
    4.   MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) );

  • 最长增长子序列 Longest Increasing SubSequence

    • 注意这里定义的状态，maxLen (k)是以s[k]做为“终点”的最长增长子序列
      1. MaxLen(1) = 1
      2. MaxLen(k) = max{MaxLen(i): 1<= i < 且k!=1}  + 1
      3. maxLen(k)的值，就是在ak左边，“终点”数值小于ak ，且长度最大的那个上升子序列的长度再加1。因为ak左边任何“终点”小于ak的子序列，加上ak后就能形成一个更长的上升子序列。