動態(tài)規(guī)劃

Dynamic Programming

簡寫為 DP，是運(yùn)籌學(xué)的一個分支，是求解決策過程最優(yōu)化的過程。20世紀(jì)50年代初，美國數(shù)學(xué)家貝爾曼（R.Bellman）等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)化原理，從而創(chuàng)立了動態(tài)規(guī)劃。動態(tài)規(guī)劃的應(yīng)用極其廣泛，包括工程技術(shù)、經(jīng)濟(jì)、工業(yè)生產(chǎn)、軍事以及自動化控制等領(lǐng)域，并在背包問題、生產(chǎn)經(jīng)營問題、資金管理問題、資源分配問題、最短路徑問題和復(fù)雜系統(tǒng)可靠性問題等中取得了顯著的效果。

動態(tài)規(guī)劃算法的基本步驟包括：

1. 確定狀態(tài)：確定需要求解的狀態(tài)，并將其表示為變量。
2. 確定狀態(tài)轉(zhuǎn)移方程：根據(jù)問題的特定約束條件和目標(biāo)函數(shù)，確定狀態(tài)之間的轉(zhuǎn)移關(guān)系，并將其表示為數(shù)學(xué)公式。
3. 初始化：為初始狀態(tài)賦初值，并將其表示為初始條件。
4. 遞推計(jì)算：根據(jù)狀態(tài)轉(zhuǎn)移方程，使用循環(huán)依次計(jì)算各個狀態(tài)的解，并將其保存在數(shù)組或表中。
5. 求解最終結(jié)果：根據(jù)問題的目標(biāo)，從計(jì)算得到的解中得出最終結(jié)果。

動態(tài)規(guī)劃算法可以用于解決各種問題，例如最短路徑問題、背包問題、最長公共子序列問題等。在實(shí)現(xiàn)動態(tài)規(guī)劃算法時，需要根據(jù)具體問題的特點(diǎn)進(jìn)行設(shè)計(jì)和調(diào)整，以確保算法的正確性和效率。

適用條件

任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動態(tài)規(guī)劃也并不是萬能的。適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。

最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）

最優(yōu)化原理可這樣闡述：一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì) [8] 。

無后效性

將各階段按照一定的次序排列好之后，對于某個給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當(dāng)前的這個狀態(tài)。換句話說，每個狀態(tài)都是過去歷史的一個完整總結(jié)。這就是無后向性，又稱為無后效性 [8] 。

子問題的重疊性

動態(tài)規(guī)劃算法的關(guān)鍵在于解決冗余，這是動態(tài)規(guī)劃算法的根本目的。動態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時間的技術(shù)，它在實(shí)現(xiàn)的過程中，不得不存儲產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其他的算法。選擇動態(tài)規(guī)劃算法是因?yàn)閯討B(tài)規(guī)劃算法在空間上可以承受，而搜索算法在時間上卻無法承受，所以我們舍空間而取時間。

真題舉例（1）

44. 通配符匹配

給定一個字符串?(s) 和一個字符模式?(p) ，實(shí)現(xiàn)一個支持?'?'?和?'*'?的通配符匹配。
'?' 可以匹配任何單個字符。'*' 可以匹配任意字符串（包括空字符串）。
兩個字符串完全匹配才算匹配成功。

說明:

• 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. 不同路徑

一個機(jī)器人位于一個?m x n?網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為 “Start” ）。
機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）。問總共有多少條不同的路徑？

示例 1：

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

示例 2：

輸入：m = 3, n = 2
輸出：3
解釋：從左上角開始，總共有 3 條路徑可以到達(dá)右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

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

示例 4：

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

提示：

• 1 <= m, n <= 100
• 題目數(shù)據(jù)保證答案小于等于?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

一個機(jī)器人位于一個?m x n?網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。

機(jī)器人每次只能向下或者向右移動一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。

現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？

網(wǎng)格中的障礙物和空位置分別用?1?和?0?來表示。

示例 1：

輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
輸出：2
解釋：3x3 網(wǎng)格的正中間有一個障礙物。從左上角到右下角一共有 2 條不同的路徑：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

輸入：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. 最小路徑和

給定一個包含非負(fù)整數(shù)的?m?x?n?網(wǎng)格?grid?，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。

說明：每次只能向下或者向右移動一步。

示例 1：

輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出：7
解釋：因?yàn)槁窂?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;
} 

續(xù)：https://hannyang.blog.csdn.net/article/details/132091605文章來源地址http://www.zghlxwxcb.cn/news/detail-625304.html

到了這里，關(guān)于力扣 C++｜一題多解之動態(tài)規(guī)劃專題（1）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！