本文共 3070 字，大约阅读时间需要 10 分钟。

动态规划经典题目：

题目描述： 给定一个m行n列的矩阵grid，从左上角开始走，每次只能往下边或者往右边走，不能走出矩阵，求最后我们走到右下角经过的路线的最小值。

分析题目：

我们每次只能走右或者下，那么你在这两种选择之间一定会有一个最优解，也就是最短的路程。这里我们假设一个m×n的矩阵来存储所有的位置的最优解。 1.初始值：dp[0][0] = grid[0][0] 2.很简单的是从上面走的话，那就是一条路走到最末尾，所以这些位置上的最优解就是直接dp[0][j] = dp[i][j-1] + grid[0][j] 同理，从最左边走的话也是一条路到头，也就是dp[i][0] = dp[i-1][0] + grid[i][j] 3.其他位置，也就是中间的那些，dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]，它只依赖与左边或者上面来的最优解。 上面这些大概看完，就可以看代码了：

1.动态规划

//时间复杂度O(m*n),空间复杂度O(m*n)int minPathSum(vector
   
    
      >& grid) {        //使用一个二维数组保存所有位置的最优解        int m = grid.size();        int n = grid[0].size();        vector
     
      
        > dp(m,vector
       
        (n));        for(int i = 0;i < m;i++)        {                for(int j = 0;j < n;j++)                {                        if(i == 0){                                if(j == 0){
  //dp[0][0]                                        dp[i][j] = grid[i][j];                                }                                else{
  //第一种情况，往右走到头                                        dp[i][j] = dp[i][j-1] + grid[i][j];                                }                        }                        else if(j == 0){
  //第二种情况，往下走到头                                dp[i][j] = dp[i-1][j] + grid[i][j];                        }                        else{                                //cout<<"min is "<
        
         <
        
       
      
     
    
   

2.优化空间的动态规划

将二维数组dp缩减为一维数组。 上面这种方法，我们将所有位置的最优解的情况都保存在了一张m×n的表中，但其实是只要我们求得最后一个数dp[m-1][n-1]即可，我们可以求出来最后一行或者最后一列，只要保证我们能走到最后的第m行或者第n列就可以找到右下角的元素。 这里我们上面是对行数m进行循环，那咱们就以一行来不断刷新，声明一个有n个元素的数组dp，也就是dp[n]，针对m不断轮询，刷新它的值，具体流程大概画了一张图片方便理解：

下面就是代码了：

//时间复杂度O(m*n)，空间复杂度O(n)int minPathSum_signal(vector
   
    
      >& grid) {        int m = grid.size();        int n = grid[0].size();        vector
     
       dp(n);        for(int i = 0;i < m;i++)        {                for(int j = 0;j < n;j++){                        if(i == 0){                                if(j == 0){                                        dp[j] = grid[i][j];                                }                                else{                                        dp[j] = dp[j-1] + grid[i][j];                                }                        }        //这里该怎么理解呢？第一次，也就是上面这个循环，更新出来了第一组dp        //之后下面首先是得到一个刷新的dp[0] = dp[0] + grid[1][0]，由于j==0这一行全部都是这么计算，就是上面的数一直加到下去，所以这里不需要更改        //得到新的dp[0]，现在相当与dp[0]往下走,dp[1]往右走，新的dp[1]就取决于dp[0] 和 dp[1] 中的最优解,更新dp[1]        //更新了dp[1]，之后，j++，现在是dp[1](新的) 和 dp[2](老的),取最优解，更新dp[2]，这里就更新完第二组了        //dp[n] = {2,101,201}        //同理，dp[0] = dp[0] + grid[2][0],之后照旧继续循环                        else if(j == 0){                                dp[j] = dp[j] + grid[i][j];                        }                        else{                                dp[j] = min(dp[j-1],dp[j]) + grid[i][j];                        }                }        }        for(int i = 0;i < n;i++)        {                cout<
      
       <<"\t";        }        cout<
      
     
    
   

本来这个博客是早就发了的，但是不小心点了编辑已经发表过的文章，然后一删除保存，全没了–| _ |–又重新理了下思路，重新写了一边，也算是教训吧，以后要多注意了.