力扣 C++｜一题多解之动态规划专题（1）

爱被打了一巴掌 2023-09-27 15:14 34阅读 0赞

![fe34a1c92c5f489689fd991ff5e0f559.png][]

## 动态规划 ##

### Dynamic Programming ###

简写为 DP，是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

动态规划算法的基本步骤包括：

1.  确定状态：确定需要求解的状态，并将其表示为变量。
2.  确定状态转移方程：根据问题的特定约束条件和目标函数，确定状态之间的转移关系，并将其表示为数学公式。
3.  初始化：为初始状态赋初值，并将其表示为初始条件。
4.  递推计算：根据状态转移方程，使用循环依次计算各个状态的解，并将其保存在数组或表中。
5.  求解最终结果：根据问题的目标，从计算得到的解中得出最终结果。

动态规划算法可以用于解决各种问题，例如最短路径问题、背包问题、最长公共子序列问题等。在实现动态规划算法时，需要根据具体问题的特点进行设计和调整，以确保算法的正确性和效率。

### 适用条件 ###

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。

### 最优化原理（最优子结构性质） ###

最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质 \[8\] 。

### 无后效性 ###

将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性 \[8\] 。

### 子问题的重叠性 ###

动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。

## 真题举例（1） ##

### 44. 通配符匹配 ###

给定一个字符串 (`s`) 和一个字符模式 (`p`) ，实现一个支持 `'?'` 和 `'*'` 的通配符匹配。  
'?' 可以匹配任何单个字符。'\*' 可以匹配任意字符串（包括空字符串）。  
两个字符串**完全匹配**才算匹配成功。

**说明:**

*  `s` 可能为空，且只包含从 `a-z` 的小写字母。
 *  `p` 可能为空，且只包含从 `a-z` 的小写字母，以及字符 `?` 和 `*`。

**示例 1:**

输入:s = "aa"  p = "a"
    输出: false
    解释: "a" 无法匹配 "aa" 整个字符串。

**示例 2:**

输入:s = "aa"  p = "*"
    输出: true
    解释: '*' 可以匹配任意字符串。

**示例 3:**

输入:s = "cb"  p = "?a"
    输出: false
    解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

**示例 4:**

输入:s = "adceb"  p = "*a*b"
    输出: true
    解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

**示例 5:**

输入:s = "acdcb"  p = "a*c?b"
    输出: false

**代码1：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        bool isMatch(string s, string p)
        {
            vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1));
            dp[0][0] = 1;
            for (int j = 1; j <= p.size(); j++)
            {
                dp[0][j] = dp[0][j - 1] && p[j - 1] == '*';
            }
            for (int i = 1; i <= s.size(); i++)
            {
                for (int j = 1; j <= p.size(); j++)
                {
                    if (p[j - 1] == '*')
                    {
                        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                    }
                    else
                    {
                        dp[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '?') && dp[i - 1][j - 1];
                    }
                }
            }
            return dp[s.size()][p.size()];
        }
    };
    
    int main()
    {
    	Solution s;
    
    	cout << s.isMatch("aa", "a") << endl;
    	cout << s.isMatch("aa", "*") << endl;
    	cout << s.isMatch("cb", "?a") << endl;
    	cout << s.isMatch("adceb", "*a*b") << endl;
    	cout << s.isMatch("acdcb", "a*c?b") << endl;
    	
    	return 0;
    }

**代码2：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        bool isMatch(string s, string p)
        {
            int m = s.size();
            int n = p.size();
    
            vector<vector<int>> dp(m + 1, vector<int>(n + 1));
            dp[0][0] = true;
    
            for (int i = 1; i <= n; i++)
            {
                if (p[i - 1] == '*')
                    dp[0][i] = true;
                else
                    break;
            }
    
            for (int i = 1; i <= m; i++)
            {
                for (int j = 1; j <= n; j++)
                {
    
                    if (p[j - 1] == '*')
                    {
                        dp[i][j] |= dp[i][j - 1];
                        dp[i][j] |= dp[i - 1][j];
                    }
                    else
                    {
                        if (p[j - 1] == '?' || s[i - 1] == p[j - 1])
                        {
                            dp[i][j] |= dp[i - 1][j - 1];
                        }
                    }
                }
            }
    
            return dp[m][n];
        }
    };
    
    int main()
    {
    	Solution s;
    
    	cout << s.isMatch("aa", "a") << endl;
    	cout << s.isMatch("aa", "*") << endl;
    	cout << s.isMatch("cb", "?a") << endl;
    	cout << s.isMatch("adceb", "*a*b") << endl;
    	cout << s.isMatch("acdcb", "a*c?b") << endl;
    	
    	return 0;
    }

**代码3：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        bool isMatch(string s, string p)
        {
            if (p.empty())
                return s.empty();
            if (s.empty())
            {
                if (p[0] == '*')
                    return isMatch(s, p.substr(1));
                else
                    return false;
            }
    
            if (p[0] == '*')
                return isMatch(s, p.substr(1)) || isMatch(s.substr(1), p);
            else
                return (s[0] == p[0] || p[0] == '?') && isMatch(s.substr(1), p.substr(1));
        }
    };
    
    int main()
    {
    	Solution s;
    
    	cout << s.isMatch("aa", "a") << endl;
    	cout << s.isMatch("aa", "*") << endl;
    	cout << s.isMatch("cb", "?a") << endl;
    	cout << s.isMatch("adceb", "*a*b") << endl;
    	cout << s.isMatch("acdcb", "a*c?b") << endl;
    	
    	return 0;
    }

**代码4：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution {
    public:
        bool isMatch(string s, string p) {
            if (s == "" && p == "" || (s == "" && p == "*"))
                return true;
            if (s == p)
                return true;
            int lens = s.length();
            int lenp = p.length();
            bool questionm = false, starm = false;
            for (int k = 0; k < lenp; k++) {
                if (p[k] == '?')
                    questionm = true;
                if (p[k] == '*')
                    starm = true;
            }
            if (lenp != lens && questionm == false && starm == false)
                return false;
            int i = 0, j = 0;
            int mstar = 0, sstar = -1;
            while (i < lens) {
                if (j < lenp && p[j] == '*') {
                    mstar = i;
                    sstar = j;
                    j += 1;
                } else if (j < lenp && (s[i] == p[j] || p[j] == '?')) {
                    i++;
                    j++;
                } else if (sstar != -1) {
                    mstar += 1;
                    j = sstar + 1;
                    i = mstar;
                } else
                    return false;
            }
            while (j < lenp) {
                if (p[j] != '*')
                    return false;
                j++;
            }
            return true;
        }
    };
    
    int main()
    {
    	Solution s;
    
    	cout << s.isMatch("aa", "a") << endl;
    	cout << s.isMatch("aa", "*") << endl;
    	cout << s.isMatch("cb", "?a") << endl;
    	cout << s.isMatch("adceb", "*a*b") << endl;
    	cout << s.isMatch("acdcb", "a*c?b") << endl;
    	
    	return 0;
    }

### 62. 不同路径 ###

一个机器人位于一个 `m x n`网格的左上角 （起始点在下图中标记为 “Start” ）。  
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

**示例 1：**

![099169dc43ebe3d42afb948803f38eda.png_pic_center][]

输入：m = 3, n = 7
    输出：28

**示例 2：**

输入：m = 3, n = 2
    输出：3
    解释：从左上角开始，总共有 3 条路径可以到达右下角。
    1. 向右 -> 向下 -> 向下
    2. 向下 -> 向下 -> 向右
    3. 向下 -> 向右 -> 向下

**示例 3：**

输入：m = 7, n = 3
    输出：28

**示例 4：**

输入：m = 3, n = 3
    输出：6

**提示：**

*  `1 <= m, n <= 100`
 *  题目数据保证答案小于等于 `2 * 10^9`

**代码1：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        int uniquePaths(int m, int n)
        {
            int N = m + n - 2;
            int M = m < n ? m - 1 : n - 1;
    
            long ans = 1;
            for (int i = 1; i <= M; i++)
                ans = ans * (N - i + 1) / i;
            return ans;
        }
    };
    
    int main()
    {
    	Solution s;
    	cout << s.uniquePaths(3, 7) << endl;
    	cout << s.uniquePaths(3, 2) << endl;
    	cout << s.uniquePaths(7, 3) << endl;
    	cout << s.uniquePaths(3, 3) << endl;
    	
    	return 0;
    }

**代码2：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        int uniquePaths(int m, int n)
        {
            if (m <= 0 || n <= 0)
            {
                return 0;
            }
    
            vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
            for (int i = 0; i < m; i++)
            {
                dp[i][0] = 1;
            }
            for (int i = 0; i < n; i++)
            {
                dp[0][i] = 1;
            }
    
            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];
        }
    };
    
    int main()
    {
    	Solution s;
    	cout << s.uniquePaths(3, 7) << endl;
    	cout << s.uniquePaths(3, 2) << endl;
    	cout << s.uniquePaths(7, 3) << endl;
    	cout << s.uniquePaths(3, 3) << endl;
    	
    	return 0;
    }

**代码3：**

#include <bits/stdc++.h>
    using namespace std;
    
    typedef vector<int> BigInt;
    class Solution
    {
    public:
        int uniquePaths(int m, int n)
        {
            if (m == 0 || n == 0)
                return 0;
            if (m == 1 || n == 1)
                return 1;
            int m_ = m - 1 + n - 1;
            int n_ = n - 1;
            BigInt a = fac(m_);
            int result = 0;
            for (int i = n_; i >= 1; i--)
                a = div(a, i);
            for (int i = m_ - n_; i >= 1; i--)
                a = div(a, i);
            int k = a.size() - 1;
            while (a[k] == 0)
                k--;
            for (int i = k; i >= 0; i--)
                result = result * 10 + a[i];
    
            return result;
        }
    
        BigInt fac(int n)
        {
            BigInt result;
            result.push_back(1);
            for (int factor = 1; factor <= n; ++factor)
            {
                long long carry = 0;
                for (auto &item : result)
                {
                    long long product = item * factor + carry;
                    item = product % 10;
                    carry = product / 10;
                }
                if (carry > 0)
                {
                    while (carry > 0)
                    {
                        result.push_back(carry % 10);
                        carry /= 10;
                    }
                }
            }
            return result;
        }
        BigInt div(BigInt a, int d)
        {
            int b = 0;
            BigInt result;
            int len = a.size();
            for (int i = len - 1; i >= 0; i--)
            {
                b = b * 10 + a[i];
                result.insert(result.begin(), b / d);
                b = b % d;
            }
            return result;
        }
    };
    
    int main()
    {
    	Solution s;
    	cout << s.uniquePaths(3, 7) << endl;
    	cout << s.uniquePaths(3, 2) << endl;
    	cout << s.uniquePaths(7, 3) << endl;
    	cout << s.uniquePaths(3, 3) << endl;
    	
    	return 0;
    }

**代码4：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution {
    public:
        int uniquePaths(int m, int n) {
            vector<vector<int>> path(m, vector<int>(n, 0));
            for (int i = 0; i < n; i++)
                path[0][i] = 1;
            for (int i = 0; i < m; i++)
                path[i][0] = 1;
            for (int i = 1; i < m; i++)
                for (int j = 1; j < n; j++)
                    path[i][j] = path[i - 1][j] + path[i][j - 1];
            return path[m - 1][n - 1];
        }
    };
    
    int main()
    {
    	Solution s;
    	cout << s.uniquePaths(3, 7) << endl;
    	cout << s.uniquePaths(3, 2) << endl;
    	cout << s.uniquePaths(7, 3) << endl;
    	cout << s.uniquePaths(3, 3) << endl;
    	
    	return 0;
    }

### 63. 不同路径 II ###

一个机器人位于一个 *m x n* 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

![dcc604a2757b6fd0e6bdc5155c945ffc.png_pic_center][]

网格中的障碍物和空位置分别用 `1` 和 `0` 来表示。

**示例 1：**

![d127c16fad8048e19db6f2a2bea73240.png_pic_center][]

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
    输出：2
    解释：3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：
    1. 向右 -> 向右 -> 向下 -> 向下
    2. 向下 -> 向下 -> 向右 -> 向右

**示例 2：**

![d95382b3c9b30e83be3e383421106a67.png_pic_center][]

输入：obstacleGrid = [[0,1],[0,0]]
    输出：1

**提示：**

*  `m == obstacleGrid.length`
 *  `n == obstacleGrid[i].length`
 *  `1 <= m, n <= 100`
 *  `obstacleGrid[i][j]` 为 `0` 或 `1`

**代码1：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
        {
            int m = obstacleGrid.size();
            int n = obstacleGrid[0].size();
            int p[m][n];
    
            int k = 0;
            while (k < m && obstacleGrid[k][0] != 1)
                p[k++][0] = 1;
    
            while (k < m)
                p[k++][0] = 0;
    
            k = 0;
            while (k < n && obstacleGrid[0][k] != 1)
                p[0][k++] = 1;
            while (k < n)
                p[0][k++] = 0;
    
            for (int i = 1; i < m; i++)
                for (int j = 1; j < n; j++)
                {
                    if (obstacleGrid[i][j] == 1)
                        p[i][j] = 0;
                    else
                        p[i][j] = p[i - 1][j] + p[i][j - 1];
                }
            return p[m - 1][n - 1];
        }
    };
    
    int main()
    {
    	Solution s;
    	vector<vector<int>> obstacleGrid = {
       {0,0,0},{0,1,0},{0,0,0}};
    	cout << s.uniquePathsWithObstacles(obstacleGrid) << endl;
    
    	obstacleGrid = {
       {0,1},{0,0}};
    	cout << s.uniquePathsWithObstacles(obstacleGrid) << endl;
    	
    	return 0;
    }

**代码2：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
        {
            int m = obstacleGrid.size(), n = obstacleGrid[0].size();
            vector<vector<int>> dp(m, vector<int>(n, 0));
            for (int i = 0; i < m && obstacleGrid[i][0] != 1; i++)
            {
                dp[i][0] = 1;
            }
            for (int i = 0; i < n && obstacleGrid[0][i] != 1; i++)
            {
                dp[0][i] = 1;
            }
            for (int i = 1; i < m; i++)
            {
                for (int j = 1; j < n; j++)
                {
                    if (obstacleGrid[i][j] != 1)
                    {
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    }
                }
            }
            return dp[m - 1][n - 1];
        }
    };
    
    int main()
    {
    	Solution s;
    	vector<vector<int>> obstacleGrid = {
       {0,0,0},{0,1,0},{0,0,0}};
    	cout << s.uniquePathsWithObstacles(obstacleGrid) << endl;
    
    	obstacleGrid = {
       {0,1,0},{0,0,0}};
    	cout << s.uniquePathsWithObstacles(obstacleGrid) << endl;
    	
    	return 0;
    }

**代码3：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
        {
            if (obstacleGrid.size() == 0 || obstacleGrid[0].size() == 0)
                return 0;
            int m = obstacleGrid.size();
            int n = obstacleGrid[0].size();
            vector<vector<int>> info(m, vector<int>(n, 0));
            for (int i = 0; i < m; ++i)
            {
                if (obstacleGrid[i][0] == 1)
                {
                    for (int j = i; j < m; j++)
                    {
                        info[j][0] = 0;
                    }
                    break;
                }
                else
                    info[i][0] = 1;
            }
            for (int i = 0; i < n; ++i)
            {
                if (obstacleGrid[0][i] == 1)
                {
                    for (int j = i; j < n; ++j)
                    {
                        info[0][j] = 0;
                    }
                    break;
                }
                else
                    info[0][i] = 1;
            }
            for (int i = 1; i < m; ++i)
            {
                for (int j = 1; j < n; ++j)
                {
                    if (obstacleGrid[i][j] == 1)
                    {
                        info[i][j] = 0;
                    }
                    else
                    {
                        info[i][j] = info[i - 1][j] + info[i][j - 1];
                    }
                }
            }
            return info[m - 1][n - 1];
        }
    };
    
    int main()
    {
    	Solution s;
    	vector<vector<int>> obstacleGrid = {
       {0,0,0},{0,1,0},{0,0,0}};
    	cout << s.uniquePathsWithObstacles(obstacleGrid) << endl;
    
    	obstacleGrid = {
       {0,1,0},{0,0,0}};
    	cout << s.uniquePathsWithObstacles(obstacleGrid) << endl;
    	
    	return 0;
    }

**代码4：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
            int m = obstacleGrid.size(), n = obstacleGrid[0].size();
            if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1)
                return 0;
            vector<vector<int>> dp(m, vector<int>(n, 0));
            dp[0][0] = 1;
            for (int i = 1; i < m; i++) {
                if (obstacleGrid[i][0] == 0)
                    dp[i][0] = dp[i - 1][0];
            }
            for (int i = 1; i < n; i++) {
                if (obstacleGrid[0][i] == 0)
                    dp[0][i] = dp[0][i - 1];
            }
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    if (obstacleGrid[i][j] == 0)
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
            return dp[m - 1][n - 1];
        }
    };
    
    int main()
    {
    	Solution s;
    	vector<vector<int>> obstacleGrid = {
       {0,0,0},{0,1,0},{0,0,0}};
    	cout << s.uniquePathsWithObstacles(obstacleGrid) << endl;
    
    	obstacleGrid = {
       {0,1,0},{0,0,0}};
    	cout << s.uniquePathsWithObstacles(obstacleGrid) << endl;
    	
    	return 0;
    }

### 64. 最小路径和 ###

给定一个包含非负整数的 `m x n` 网格 `grid` ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

**示例 1：**

![0c6d9496445c66b255a406ba2f9a3eb9.png_pic_center][]

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
    输出：7
    解释：因为路径 1→3→1→1→1 的总和最小。

**示例 2：**

输入：grid = [[1,2,3],[4,5,6]]
    输出：12

**提示：**

*  `m == grid.length`
 *  `n == grid[i].length`
 *  `1 <= m, n <= 200`
 *  `0 <= grid[i][j] <= 100`

**代码1：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        int minPathSum(vector<vector<int>> &grid)
        {
            if (grid.size() == 0)
                return 0;
            int m = grid.size();
            int n = grid[0].size();
            vector<vector<int>> m_memo = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
    
            for (int i = n - 1; i >= 0; --i)
                m_memo[m - 1][i] = grid[m - 1][i] + m_memo[m - 1][i + 1];
            for (int j = m - 1; j >= 0; --j)
                m_memo[j][n - 1] = grid[j][n - 1] + m_memo[j + 1][n - 1];
    
            for (int i = m - 2; i >= 0; --i)
            {
                for (int j = n - 2; j >= 0; --j)
                {
                    m_memo[i][j] = grid[i][j] + min(m_memo[i][j + 1], m_memo[i + 1][j]);
                }
            }
            return m_memo[0][0];
        }
    };
    
    int main()
    {
    	Solution s;
    	vector<vector<int>> grid = {
       {1,3,1},{1,5,1},{4,2,1}};
    	cout << s.minPathSum(grid) << endl;
    	
    	grid = {
       {1,2,3},{4,5,6}};
    	cout << s.minPathSum(grid) << endl;
    	
    	return 0;
    }

**代码2：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        int minPathSum(vector<vector<int>> &grid)
        {
            int row = grid.size();
            int column = grid[0].size();
            for (int i = 1; i < column; ++i)
            {
                grid[0][i] = grid[0][i - 1] + grid[0][i];
            }
            for (int i = 1; i < row; ++i)
            {
                grid[i][0] = grid[i - 1][0] + grid[i][0];
            }
            for (int i = 1; i < row; ++i)
            {
                for (int j = 1; j < column; ++j)
                {
                    int temp = grid[i - 1][j] > grid[i][j - 1] ? grid[i][j - 1] : grid[i - 1][j];
                    grid[i][j] = grid[i][j] + temp;
                }
            }
            return grid[row - 1][column - 1];
        }
    };
    
    int main()
    {
    	Solution s;
    	vector<vector<int>> grid = {
       {1,3,1},{1,5,1},{4,2,1}};
    	cout << s.minPathSum(grid) << endl;
    	
    	grid = {
       {1,2,3},{4,5,6}};
    	cout << s.minPathSum(grid) << endl;
    	
    	return 0;
    }

**代码3：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution
    {
    public:
        int minPathSum(vector<vector<int>> &grid)
        {
            int row = grid.size();
            int col = grid[0].size();
            vector<int> f(col, 0);
    
            for (int i = 0; i < row; ++i)
            {
                f[0] = f[0] + grid[i][0];
                for (int j = 1; j < col; ++j)
                {
                    if (i == 0)
                        f[j] = f[j - 1] + grid[i][j];
                    else
                        f[j] = min(f[j - 1], f[j]) + grid[i][j];
                }
            }
            return f[col - 1];
        }
    };
    
    int main()
    {
    	Solution s;
    	vector<vector<int>> grid = {
       {1,3,1},{1,5,1},{4,2,1}};
    	cout << s.minPathSum(grid) << endl;
    	
    	grid = {
       {1,2,3},{4,5,6}};
    	cout << s.minPathSum(grid) << endl;
    	
    	return 0;
    }

**代码4：**

#include <bits/stdc++.h>
    using namespace std;
    
    class Solution {
    private:
        int m, n;
        int memo[100][100];
    public:
        int minPathSum(vector<vector<int>> &grid) {
            m = grid.size(), n = grid[0].size();
            for (int i = 0; i < m; i++) {
                memset(memo[i], -1, sizeof(int) * n);
            }
            return dfs(grid, 0, 0);
        }
        int dfs(vector<vector<int>> &grid, int r, int c) {
            if (r < 0 || r >= m || c < 0 || c >= n)
                return 1000000;
            if (memo[r][c] != -1)
                return memo[r][c];
            if (r == m - 1 && c == n - 1) {
                memo[r][c] = grid[m - 1][n - 1];
                return memo[r][c];
            }
            int right = dfs(grid, r, c + 1);
            int down = dfs(grid, r + 1, c);
            memo[r][c] = min(right, down) + grid[r][c];
            return memo[r][c];
        }
    };
    
    int main()
    {
    	Solution s;
    	vector<vector<int>> grid = {
       {1,3,1},{1,5,1},{4,2,1}};
    	cout << s.minPathSum(grid) << endl;
    	
    	grid = {
       {1,2,3},{4,5,6}};
    	cout << s.minPathSum(grid) << endl;
    	
    	return 0;
    }

--------------------

续：[https://hannyang.blog.csdn.net/article/details/132091605][https_hannyang.blog.csdn.net_article_details_132091605]

[fe34a1c92c5f489689fd991ff5e0f559.png]: https://img-blog.csdnimg.cn/fe34a1c92c5f489689fd991ff5e0f559.png
[099169dc43ebe3d42afb948803f38eda.png_pic_center]: https://img-blog.csdnimg.cn/img_convert/099169dc43ebe3d42afb948803f38eda.png#pic_center
[dcc604a2757b6fd0e6bdc5155c945ffc.png_pic_center]: https://img-blog.csdnimg.cn/img_convert/dcc604a2757b6fd0e6bdc5155c945ffc.png#pic_center
[d127c16fad8048e19db6f2a2bea73240.png_pic_center]: https://img-blog.csdnimg.cn/img_convert/d127c16fad8048e19db6f2a2bea73240.png#pic_center
[d95382b3c9b30e83be3e383421106a67.png_pic_center]: https://img-blog.csdnimg.cn/img_convert/d95382b3c9b30e83be3e383421106a67.png#pic_center
[0c6d9496445c66b255a406ba2f9a3eb9.png_pic_center]: https://img-blog.csdnimg.cn/img_convert/0c6d9496445c66b255a406ba2f9a3eb9.png#pic_center
[https_hannyang.blog.csdn.net_article_details_132091605]: https://hannyang.blog.csdn.net/article/details/132091605