动态规划之旅

一、浅谈
就现在的了解，动态规划的特点就是：具备最有子结构，全局解可以通过最优子结构递推求得的算法。它与二分查找有一定的相似性，都是找最优解。但他们是有区别的，二分查找是明确在已给的约束条件下存在一个最优解，而动规是有明确的最优子结构并且可以通过最优子结构来得到全局的最优解。
二、动规的一般步骤

先确定dp的含义
找到base case(边界)
找到递推方程/状态转移方程
其中，第一步的关键是找到一个很好表征所要结果并且有一定递推关系的dp数组；
第二步的关键是要考虑边界情况；
第三步的关键是要找到不同状态之间的转移关系。

三、题目

不同路径
第一步，确定dp含义。与坐标有关的题目，都比较好确定dp的含义。像这个题的话，dp[i][j]即可表征，从start到[i,j]的路径总数。
第二步，找base case。由于只能向右或向下移动，因此，dp[0][]=dp[][0]=1;
第三步，找状态转移方程，显然，到达dp[i][j]只有两种方式，从左边或上边，因此dp[i][j]=dp[i-1][j]+dp[i][j-1];
这样题目就可以解决了。

 int uniquePaths(int m, int n) {
     //dp:描述为 到达坐标 i,j 的路径数 
     vector<vector<int>>dp(m,vector<int>(n));
     //base case 
     for(int i=0;i<n;++i)    dp[0][i]=1;
     for(int i=1;i<m;++i)    dp[i][0]=1;
     //recursion
     //到达一个地方的路径数就是 到达左边和上边的路径数之和
     for(int i=1;i<m;++i){
         for(int j=1;j<n;++j){
             dp[i][j]=dp[i-1][j]+dp[i][j-1];
         }
     }
     return dp[m-1][n-1];
 }

不同路径 II
这个题与上面这个题差不多，只是多了一个障碍物，也就是第二步和第三步的状态转移出现了一点变化。
不再赘述。上代码

 int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
     const int m=obstacleGrid.size();
     const int n=obstacleGrid[0].size();
     //dp
     vector<vector<int>>dp(m,vector<int>(n));
     //base case
     for(int i=0;i<n;++i) {
         if(obstacleGrid[0][i]){
             while(i<n)  dp[0][i++]=0;
             break;
         }
         else dp[0][i]=1;
     }
     for(int i=0;i<m;++i) {
         if(obstacleGrid[i][0]){
             while(i<m)  dp[i++][0]=0;
             break;
         }
         else dp[i][0]=1;
     }
     //recursion
     for(int i=1;i<m;++i){
         for(int j=1;j<n;++j){
             if(obstacleGrid[i][j])  dp[i][j]=0;
             else dp[i][j]=dp[i-1][j]+dp[i][j-1];
         }
     }
     return dp[m-1][n-1];
 }

最小路径和
第一步，明确dp，坐标相关，直接让dp[i][j]表示从start到[i,j]的最小路径
第二步，找到base case。第一行和第一列显然就是边界，直接累加求出dp[i][]，dp[][j]
第三步，找到状态转移方程。不难想到，只要每一次都选择到达[i,j]的两种方式中，已有路长短的，则加上到达[i,j]所需路长也将是最短的。即dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
上代码：

 int minPathSum(vector<vector<int>>& grid) {
     const int m=grid.size();
     const int n=grid[0].size();
     //dp
     vector<vector<int>>dp(m,vector<int>(n));
     //base case
     dp[0][0]=grid[0][0]; 
     for(int i=1;i<n;++i)
         dp[0][i]=dp[0][i-1]+grid[0][i];
     for(int i=1;i<m;++i)
         dp[i][0]=dp[i-1][0]+grid[i][0];
     //recursion
     for(int i=1;i<m;++i){
         for(int j=1;j<n;++j){
             dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
         }
     }
     return dp[m-1][n-1];
 }

解码方法
第一步，明确dp含义。字符串问题且只有字符的位置有关，因此只需要一维dp[i]，表示截至第i个字符，整个字符串可解码出的可能结果总数。关于字符串的dp往往要增加一位，从而让dp下标对应实际的位序，因此在字符串下标取值时就要进行-1操作。
第二步，找到base case。当没有字符时，解码方法只有1种，dp[0]=1;
第三步，找到状态转移方程。由题目条件可知道，dp[i]可由两种方式得到，
一种是，只编码一个字符，则只要当前第i个字符(对于字符串中[i-1]字符)不是'0'，有dp[i]+=dp[i-1];
另一种是，编码两个字符(i和i-1，对应[i-1]和[i-2])，此时只要i-1([i-2])位不是'0'，且两个字符不超过26，就可以用这两个字符编码，有dp[i]+=dp[i-2];
这个题主要难点就是要找到状态转移方程。
上代码：
```
 int numDecodings(string s) {
     const int n=s.size();
     //用另一种思维
     //dp:表示到第i个字符编码总数
     vector<int>dp(n+1);//因为dp从1开始对应s从0开始，因此s的要减1
     //base case 
     dp[0]=1;
     //recursion
     for(int i=1;i<=n;++i){
         if(s[i-1]!='0')   dp[i]+=dp[i-1];
         if(i>1&&s[i-2]!='0'&&(s[i-2]-'0')*10+(s[i-1]-'0')<=26 )      dp[i]+=dp[i-2];           
     }  
     return dp[n];
 }
```

1143. 最长公共子序列
像这种涉及两个字符串的，一般需要二维dp，且扩一位。
第一步，明确dp，dp[i][j]表示截至text1的第i个元素，截至text2的第j个元素，两串的最长公共子序列长度
第二步，找到base case，当i==0||j==0时，显然，dp都等于0
第三步，找到状态转移方程，当此时两串的字符对应相同，即text1[i]==text2[j]时，dp[i][j]=d[i-1][j-1]+1;
当两串的字符不同时，dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

 int longestCommonSubsequence(string text1, string text2) {
     const int m=text1.size();const int n=text2.size();
     //dp
     vector<vector<int>>dp(m+1,vector<int>(n+1));
     //base case
     for(int i=0;i<=m;++i)   dp[i][0]=0;
     for(int i=0;i<=n;++i)   dp[0][i]=0;
     //recursion
     for(int i=1;i<=m;++i){
         for(int j=1;j<=n;++j){
             if(text1[i-1]==text2[j-1])
                 dp[i][j]=dp[i-1][j-1]+1;
             else    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
         }
     }
     return dp[m][n];
 }

最长公共子串
解题思路类似最长公共子序列，但是，求的是公共子串而非序列，因此dp的含义与转移方程发生了点变化。
dp[i][j]表示以str1的第i个元素结尾，以str2的第j个元素结尾(不管哪里是开头)时，最长公共子串的长度
状态转移方程变为：str1[i-1]==str2[j-1]时，dp[i][j]=dp[i-1][j-1]+1；不等时，dp[i][j]=0;
同时注意，我们此时得到的dp并不能直接得到我们最终的最长公共子串，我们需要获取dp中最大的值，以及对应的起始字符位置以得到最长公共子串。

 string LCS(string str1, string str2) {
     // write code here
     const int m=str1.size();const int n=str2.size();
     int maxindex=0,maxlenth=0;
     //dp
     vector<vector<int>>dp(m+1,vector<int>(n+1));
     //base case
     for(int i=0;i<=m;++i)    dp[i][0]=0;
     for(int i=0;i<=n;++i)    dp[0][i]=0;
     //recursion
     for(int i=1;i<=m;++i){
         for(int j=1;j<=n;++j){
             if(str1[i-1]==str2[j-1])
                 dp[i][j]=dp[i-1][j-1]+1;
             else    dp[i][j]=0;
             if(maxlenth<dp[i][j]){
                 maxlenth=dp[i][j];
                 maxindex=i;
             }
         }
     }
     return maxlenth? str1.substr(maxindex-maxlenth,maxlenth):"-1";
 }

95. 不同的二叉搜索树 II
这个题比较复杂，主要的核心技巧思路来源于，节点的值来自[1,n]的递增序列。
遍历所有可能并记录：以每一个值作为根节点，计算左树可能结构x右树可能结构，得到的就是以该值为根节点的BST可能结构数
难点在于统计结构树的同时还要建树

  vector<TreeNode*> generateTrees(int n) {
      //dp
      vector<vector<TreeNode*>>dp(n+1);
      //base case
      dp[0].push_back(nullptr);
      //recursion
      for(int i=1;i<=n;++i){//记录dp[i]：左树的可能结构数
          for(int root=1;root<=i;++root){//以每个数作为根节点遍历结果
              int left=root-1;//左树节点数
              int right=i-root;//右树节点数
              for(auto lefttree:dp[left]){//遍历左树可能结构
                  for(auto righttree:dp[right]){//遍历右树可能结构，恰与左树有关联，可转换为左树
                      TreeNode *newroot=new TreeNode(root);
                      newroot->left=lefttree;
                      newroot->right=clone(root,righttree);//调用clone函数，实现将dp[i]中左树结构变为右树
                      dp[i].push_back(newroot);
                  }
              }
          }
      }
      return dp[n];

  }
  TreeNode *clone(int root_val,TreeNode *root){
      //base case
      if(!root)   return nullptr;
      //operations
      TreeNode *newroot=new TreeNode(root->val+root_val);
      newroot->left=clone(root_val,root->left);
      newroot->right=clone(root_val,root->right);
      return newroot;
  }