{"id":1744,"date":"2024-11-22T16:11:11","date_gmt":"2024-11-22T08:11:11","guid":{"rendered":"http:\/\/114.55.108.251\/?p=1744"},"modified":"2025-03-19T22:22:34","modified_gmt":"2025-03-19T14:22:34","slug":"leetcode-hot100%e5%8a%a8%e6%80%81%e8%a7%84%e5%88%92","status":"publish","type":"post","link":"https:\/\/guapicoding.com\/?p=1744","title":{"rendered":"LeetCode hot100@\u52a8\u6001\u89c4\u5212&\u591a\u7ef4\u52a8\u6001\u89c4\u5212"},"content":{"rendered":"\n

More content<\/strong><\/em>\uff1a<\/em><\/strong>\u529b\u6263\u9898\u8bb0\u4e4b\u52a8\u6001\u89c4\u5212<\/a><\/p>\n\n\n\n

70. \u722c\u697c\u68af<\/a>\u2705<\/h2>\n\n\n\n

dp\u6570\u7ec4\u4e0b\u6807\u4ee3\u8868\u5f53\u524d\u5728\u7b2c\u51e0\u9636\uff0c\u6570\u7ec4value\u8868\u793a\u5230\u8fd9\u4e00\u9636\u7684\u65b9\u6cd5\u6570<\/strong><\/em>\uff08\u5373\u722c\u5230\u7b2ci\u5c42\u697c\u68af\uff0c\u6709dp[i]\u79cd\u65b9\u6cd5\uff09<\/em><\/strong><\/p>\n\n\n\n

\u904d\u5386\u987a\u5e8f\u4ece\u524d\u5f80\u540e \u4f46\u662f\u4e00\u5f00\u59cb\u6ca1\u60f3\u660e\u767d\u4e3a\u4ec0\u4e48\u72b6\u6001\u8f6c\u79fb\u516c\u5f0f\u662fdp[i] = dp[i-1] + dp[i-2]<\/em><\/strong> \u53ea\u662f\u627e\u89c4\u5f8b\u63a8\u51fa\u6765\u7684<\/em><\/strong><\/p>\n\n\n\n

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(50); \/\/dp\u6570\u7ec4\u4e0b\u6807\u4ee3\u8868\u5f53\u524d\u5728\u7b2c\u51e0\u9636\uff0c\u6570\u7ec4value\u8868\u793a\u5230\u8fd9\u4e00\u9636\u7684\u65b9\u6cd5\u6570
        dp[1] = 1;
        dp[2] = 2;
        if(n < 3) return dp[n];
        for(int i = 3; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];

        return dp[n];
    }
};<\/code><\/pre>\n\n\n\n
\n\n\n\n
118. \u6768\u8f89\u4e09\u89d2<\/a>\u2705<\/h2>\n\n\n\n
dp\u6570\u7ec4\u542b\u4e49\uff1adp[i][j]\u4e3a\u7b2ci+1\u884c\u7684\u7b2cj+1\u4e2a\u6570\u503c<\/p>\n\n\n\n
\u4f9d\u636e\u6768\u8f89\u4e09\u89d2\u7684\u5b9a\u4e49\u6a21\u62dfDP\u5373\u53ef<\/p>\n\n\n\n
class Solution {\npublic:\n    vector<vector<int>> generate(int numRows) {\n        vector<vector<int>> dp;\n        for(int i = 0; i < numRows; i++) {\n            vector<int> v(i+1, 0);\n            dp.push_back(v);\n            dp[i][0] = 1;\n            dp[i][i] = 1;\n        }\n \n        for(int i = 2; i < numRows; i++) {\n            for(int j = 1; j < i; j++) {\n                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];\n            }\n        }\n        \n        return dp;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
198. \u6253\u5bb6\u52ab\u820d<\/a>\u2705<\/h2>\n\n\n\n
dp\u6570\u7ec4\u542b\u4e49\uff1a\u524di\u95f4\u623f\u5c4b\u80fd\u5077\u7684\u6700\u9ad8\u91d1\u989d\u4e3adp[i]<\/em><\/strong><\/p>\n\n\n\n
\u521d\u59cb\u5316\uff1adp[0]=nums[0]\uff08\u4e0b\u6807\u4e3a0\u4e5f\u5c31\u662f\u7b2c\u4e00\u95f4\u623f\u5c4b\uff0c\u80fd\u5077\u7684\u6700\u9ad8\u91d1\u989d\u81ea\u7136\u4e3anums[0]\uff09\uff0cdp[1] = max(nums[0], nums[1])\uff08\u76f8\u90bb\u7684\u4e24\u95f4\u623f\u53ea\u80fd\u5077\u4e00\u4e2a\uff0c\u56e0\u6b64\u54ea\u4e2a\u91d1\u989d\u9ad8\u5c31\u5077\u54ea\u4e2a\uff09<\/strong><\/em><\/p>\n\n\n\n
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];

        vector<uint64_t> dp(nums.size() + 1, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for(int i = 2; i < nums.size(); i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]); \/\/\u7b2ci\u5bb6\u5077or\u4e0d\u5077
            \/\/ cout << \"dp[\" << i << \"] = \" << dp[i] << endl;
        }

        return dp[nums.size()-1];   
    }
};<\/code><\/pre>\n\n\n\n
\n\n\n\n
279. \u5b8c\u5168\u5e73\u65b9\u6570<\/a>\u274c<\/h2>\n\n\n\n
\u6ca1\u60f3\u5230\u662f\u5b8c\u5168\u80cc\u5305\u95ee\u9898<\/em><\/strong>!<\/strong><\/em><\/p>\n\n\n\n
\u6bcf\u4e2a\u5b8c\u5168\u5e73\u65b9\u6570\u90fd\u53ef\u4ee5\u91cd\u590d\u7528 \u56e0\u6b64\u5b8c\u5168\u80cc\u5305<\/em><\/strong><\/p>\n\n\n\n
\u6c42\u6700\u5c11\u6570\u91cf \u8ddf322. \u96f6\u94b1\u5151\u6362<\/a>\u5f88\u76f8\u4f3c \u53ea\u9700\u8981\u628a\u7269\u54c1\u4ece\u786c\u5e01\u6362\u6210\u5b8c\u5168\u5e73\u65b9\u6570\u5373\u53ef<\/strong><\/em><\/p>\n\n\n\n
class Solution {\npublic:\n    int numSquares(int n) {\n        \/\/\u5f53n\u4e3ai\u65f6\uff0c\u51d1\u6ee1n\u9700\u8981\u7684\u6700\u5c11\u5b8c\u5168\u5e73\u65b9\u6570\u7684\u4e2a\u6570\u4e3adp[i]\n        vector<int> dp(n + 1, INT_MAX);\n        dp[0] = 0;\n\n        for(int i = 1; i * i < 10001; i++) {\n            for(int j = i * i; j <= n; j++) {\n                dp[j] = min(dp[j], dp[j-i*i] + 1);\n            }\n        }\n\n        return dp[n];\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
322. \u96f6\u94b1\u5151\u6362<\/a>\u2705<\/h2>\n\n\n\n
\u8ddf\u4e0a\u9898279. \u5b8c\u5168\u5e73\u65b9\u6570<\/a>\u540c\u7406 \u5b8c\u5168\u80cc\u5305<\/strong><\/em><\/p>\n\n\n\n
\u6ce8\u610f\u6570\u7ec4\u6570\u636e\u7c7b\u578b\u4e3auint64_t \u5426\u5219\u4f1a\u6ea2\u51fa<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    int coinChange(vector<int>& coins, int amount) {\n        \/\/\u51d1\u6210\u603b\u91d1\u989di\u7684\u6700\u5c11\u786c\u5e01\u4e2a\u6570\u4e3adp[i]\n        vector<uint64_t> dp(amount + 1, INT_MAX);\n        dp[0] = 0;\n\n        for(int i = 0; i < coins.size(); i++) {\n            for(int j = coins[i]; j <= amount; j++) {\n                dp[j] = min(dp[j], dp[j-coins[i]] + 1);\n            }\n        }\n\n        if(dp[amount] == INT_MAX) return -1;\n        return dp[amount];\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
139. \u5355\u8bcd\u62c6\u5206<\/a>\u274c<\/h2>\n\n\n\n
\u5b8c\u5168\u80cc\u5305 \u4f46\u8fd9\u662f\u4e00\u4e2a\u6392\u5217\u95ee\u9898 \u56e0\u6b64\u5728\u904d\u5386\u65f6\u5fc5\u987b\u5148\u904d\u5386\u5bb9\u91cf\u518d\u904d\u5386\u7269\u54c1<\/strong><\/em><\/p>\n\n\n\n
\u5426\u5219\u5bf9\u4e8e\u793a\u4f8b2\uff1as = “applepenapple”, wordDict = [“apple”, “pen”] apple\u53ea\u4f1a\u51fa\u73b0\u5728\u5934\u90e8 \u800c\u4e0d\u4f1a\u518d\u6b21\u51fa\u73b0\u5728\u5c3e\u90e8 \u56e0\u4e3a\u7269\u54c1\u904d\u5386\u4e00\u6b21\u5c31\u6ca1\u4e86 \u5176\u5b83\u5bb9\u91cf\u6765\u7ee7\u627f\u5b83\u7684\u72b6\u6001 apple\u4e5f\u53ea\u4f1a\u51fa\u73b0\u5728\u5934\u90e8<\/strong><\/em><\/p>\n\n\n\n
class Solution {\npublic:\n    bool wordBreak(string s, vector<string>& wordDict) {\n        \/\/\u62fc\u51fa\u76ee\u6807\u5b57\u7b26\u4e32\u524di\u4e2a\u5b57\u7b26\u6240\u9700\u8981\u7684\u6700\u5c11\u5355\u8bcd\u6570\u4e3adp[i]\n        vector<uint64_t> dp(s.size()+1, INT_MAX);\n        dp[0] = 0;\n\n        for(int i = 0; i <= s.size(); i++) {\/\/\u5148\u904d\u5386\u5bb9\u91cf\n            for(int j = 0; j < wordDict.size(); j++) { \/\/\u518d\u904d\u5386\u7269\u54c1\n                if(i >= wordDict[j].size() && s.substr(i-wordDict[j].size(), wordDict[j].size()) == wordDict[j]) {\n                    dp[i] = min(dp[i], dp[i-wordDict[j].size()] + 1); \n                } \n            }\n        }\n\n        if(dp[s.size()] == INT_MAX) return false;\n        return true;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
\u203b300. \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217<\/a>\u2705\u4e24\u4e2a\u53d8\u5f0f<\/h2>\n\n\n\n
dp\u6570\u7ec4\u542b\u4e49\uff1a\u4e0b\u6807\u4ece0\u5230i\u7684\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\u662fdp[i]<\/em><\/strong><\/p>\n\n\n\n
\u5148\u904d\u5386\u957f\u5ea6\uff0c\u518d\u904d\u5386\u4e4b\u524d\u7684\u6bcf\u4e00\u4e2a\u72b6\u6001<\/strong><\/em><\/p>\n\n\n\n
\u6269\u5c551\uff1a\u73b0\u5728\u4e0d\u8981\u6c42\u8f93\u51fa\u957f\u5ea6\uff0c\u800c\u662f\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u672c\u8eab<\/em>\uff08\u5982\u679c\u6709\u591a\u4e2a\uff0c\u8f93\u51fa\u4efb\u610f\u4e00\u4e2a\uff09<\/p>\n\n\n\n
\u6269\u5c552\uff1a\u73b0\u5728\u4e0d\u8981\u6c42\u8f93\u51fa\u957f\u5ea6\uff0c\u800c\u662f\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u672c\u8eab<\/em>\uff08\u5982\u679c\u6709\u591a\u4e2a\uff0c\u8f93\u51fa\u5b57\u5178\u5e8f\u6700\u5c0f\u7684\u90a3\u4e2a\uff09<\/p>\n\n\n\n
class Solution {\npublic:\n    int lengthOfLIS(vector<int>& nums) {\n        \/\/\u4e0b\u6807\u4ece0\u5230i\u7684\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\u662fdp[i]\n        vector<int> dp(nums.size() + 1, 1);\n        int res = 1;\n\n        for(int i = 1; i < nums.size(); i++) {\n            for(int j = 0; j < i; j++) {\n                if(nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);\n            }  \n            res = max(res, dp[i]);\n            \/\/ cout << \"dp[\" << i << \"] = \" << dp[i] << endl;\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n
class \u6269\u5c551 {\npublic:\n    int lengthOfLIS(vector<int>& nums) {\n        int max_len = 1; \/\/ \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\n        int end_index = 0; \/\/ \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u5c3e\u90e8\u7d22\u5f15\n        \/\/ \u6570\u7ec4\u4e0b\u6807[0:i]\u7684\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\u4e3adp[i]\n        vector<int> dp(nums.size(), 1);\n        \/\/ \u8bb0\u5f55\u6bcf\u4e2a\u4f4d\u7f6e\u7684\u524d\u9a71\u8282\u70b9\n        vector<int> prev(nums.size(), -1);\n        for(int i = 1; i < nums.size(); i++) {\n            for(int j = 0; j < i; j++) {\n                if(nums[i] > nums[j] && dp[j] + 1 > dp[i]) {\n                    dp[i] = dp[j] + 1;\n                    prev[i] = j; \/\/ \u66f4\u65b0\u524d\u9a71\u8282\u70b9\n                }  \n            }\n            if(dp[i] > max_len) {\n                max_len = dp[i];\n                end_index = i;\n            }\n        }\n        \/\/ \u56de\u6eaf\u6784\u9020\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\n        vector<int> lis;\n        while(end_index != -1) {\n            lis.push_back(nums[end_index]);\n            end_index = prev[end_index];\n        }\n        reverse(lis.begin(), lis.end());\n        \n        for(int &x : lis) cout << x << \" \";\n        \n        return 1;\n    }\n};<\/code><\/pre>\n\n\n\n
class \u6269\u5c552 {\npublic:\n    int lengthOfLIS(vector<int>& nums) {\n        int max_len = 1; \/\/ \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\n        int end_index = 0; \/\/ \u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u5c3e\u90e8\u7d22\u5f15\n        \/\/ \u6570\u7ec4\u4e0b\u6807[0:i]\u7684\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\u7684\u957f\u5ea6\u4e3adp[i]\n        vector<int> dp(nums.size(), 1);\n        \/\/ \u8bb0\u5f55\u6bcf\u4e2a\u4f4d\u7f6e\u7684\u524d\u9a71\u8282\u70b9\n        vector<int> prev(nums.size(), -1);\n        for(int i = 1; i < nums.size(); i++) {\n            for(int j = 0; j < i; j++) {\n                if(nums[i] > nums[j]) {\n                    if(dp[j] + 1 > dp[i]) { \/\/ \u80fd\u5ef6\u957f\u5b50\u5e8f\u5217\n                        dp[i] = dp[j] + 1;\n                        prev[i] = j; \/\/ \u66f4\u65b0\u524d\u9a71\u8282\u70b9\n                    } else if(dp[j] + 1 == dp[i]) { \/\/ \u957f\u5ea6\u76f8\u540c\uff0c\u9009\u62e9\u5b57\u5178\u5e8f\u66f4\u5c0f\u7684\n                        if(prev[i] == -1 || nums[j] < nums[prev[i]]) {\n                            prev[i] = j; \n                        }\n                    }\n                    \n                }  \n            }\n            \/\/ \u66f4\u65b0\u6700\u957f\u5b50\u5e8f\u5217\u7684\u5c3e\u90e8\u7d22\u5f15\n            if(dp[i] > max_len) {\n                max_len = dp[i];\n                end_index = i;\n            } else if(dp[i] == max_len) {\n                \/\/ \u5982\u679c\u957f\u5ea6\u76f8\u540c\uff0c\u9009\u62e9\u5b57\u5178\u5e8f\u7684\u90a3\u4e2a\n                if(nums[i] < nums[end_index]) end_index = i;\n            }\n        }\n        \/\/ \u56de\u6eaf\u6784\u9020\u6700\u957f\u9012\u589e\u5b50\u5e8f\u5217\n        vector<int> lis;\n        while(end_index != -1) {\n            lis.push_back(nums[end_index]);\n            end_index = prev[end_index];\n        }\n        reverse(lis.begin(), lis.end());\n        \n        for(int &x : lis) cout << x << \" \";\n        \n        return 1;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
152. \u4e58\u79ef\u6700\u5927\u5b50\u6570\u7ec4<\/a>\u274c<\/h2>\n\n\n\n
\u8fde\u7eed\u7684\u5b50\u5e8f\u5217\u95ee\u9898 \u672c\u9898\u662f 53. \u6700\u5927\u5b50\u6570\u7ec4\u548c<\/a> \u7684\u4e58\u6cd5\u7248\u672c<\/em><\/strong><\/p>\n\n\n\n
\u6ca1\u60f3\u5230\u8981\u7528\u4e24\u4e2adp\u6570\u7ec4<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    int maxProduct(vector<int>& nums) {\n        int res = -INT_MAX;\n        if(nums.size() == 1) return nums[0];\n        \/\/\u4ee5\u4e0b\u6807i\u7ed3\u5c3e\u7684\u8fde\u7eed\u5b50\u6570\u7ec4\u7684\u6700\u5927\u4e58\u79ef\u4e3adpMax[i]\n        \/\/\u4ee5\u4e0b\u6807i\u7ed3\u5c3e\u7684\u8fde\u7eed\u5b50\u6570\u7ec4\u7684\u6700\u5c0f\u4e58\u79ef\u4e3adpMin[i]\n        vector<int> dpMax(nums.size() + 1, 0);\n        vector<int> dpMin(nums.size() + 1, 0);\n        dpMax[0] = nums[0];\n        dpMin[0] = nums[0];\n \n        for(int i = 1; i < nums.size(); i++) {\n            \/\/{} \u662f\u521d\u59cb\u5316\u5217\u8868\u7684\u8bed\u6cd5\uff0c\u7528\u4e8e\u8ba9 std::max \u540c\u65f6\u5904\u7406\u591a\u4e2a\u503c \n            dpMax[i] = max({nums[i] * dpMax[i-1], nums[i] * dpMin[i-1], nums[i]});\n            dpMin[i] = min({nums[i] * dpMax[i-1], nums[i] * dpMin[i-1], nums[i]});\n        }\n\n        return ranges::max(dpMax);\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
416. \u5206\u5272\u7b49\u548c\u5b50\u96c6<\/a>\u2705<\/h2>\n\n\n\n
\u4e00\u773c01\u80cc\u5305\u53d8\u5f0f <\/em><\/strong>\u7269\u54c1\u7684\u91cd\u91cf\u548c\u4ef7\u503c\u76f8\u7b49<\/strong><\/em><\/p>\n\n\n\n
\u80cc\u5305\u5bb9\u91cf\u8bbe\u4e3a\u5143\u7d20\u603b\u548c\u4e00\u534a \u770b\u80fd\u5426\u6070\u597d\u585e\u5165\u82e5\u5e72\u5143\u7d20\u5373\u53ef<\/strong><\/em><\/p>\n\n\n\n
class Solution {\npublic:\n    bool canPartition(vector<int>& nums) {\n        \/\/01\u80cc\u5305\n        int sum = 0;\n        for(const auto &i : nums) sum += i;\n\n        if(sum % 2) return false; \/\/\u5947\u6570\n\n        sum \/= 2; \/\/\u80cc\u5305\u5bb9\u91cf\n        vector<int> dp(sum + 1, 0);\n\n        for(int i = 0; i < nums.size(); i++) {\n            for(int j = sum; j >= nums[i]; j--) {\n                dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]);\n                \/\/ cout << \"i = \" << i << \", dp[\" << j << \"] = \" << dp[j] << endl;\n            }\n        }\n\n        if(dp[sum] == sum) return true; \/\/\u6070\u597d\u88c5\u8fdb\u53bb\n        return false; \n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
32. \u6700\u957f\u6709\u6548\u62ec\u53f7<\/a>\u274c<\/h2>\n\n\n\n
\u8fde\u7eed\u7684\u5b50\u5e8f\u5217\u95ee\u9898<\/em><\/strong><\/p>\n\n\n\n
\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\u6ca1\u60f3\u51fa\u6765<\/strong><\/em><\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
class Solution {\npublic:\n    int longestValidParentheses(string s) {\n        if(s.size() < 2) return 0;\n        \/\/\u4ee5\u4e0b\u6807i\u7ed3\u5c3e\u7684\u6700\u957f\u6709\u6548\u62ec\u53f7\u5b50\u4e32\u957f\u5ea6\u662fdp[i]\n        vector<int> dp(s.size(), 0);\n  \n\n        for(int i = 1; i < s.size(); i++) {\n            if(s[i] == '(') continue; \/\/\u53ea\u8003\u8651')'\n            \n            if(s[i-1] == '(') {\n                if(i >= 2) dp[i] = dp[i-2] + 2;\n                else dp[i] = 2; \/\/\u8003\u8651\u60c5\u51b5\uff1ai = 1, s = \"()\"\n            } else if(i - dp[i-1] - 1 >= 0 && s[i - dp[i-1] - 1] == '(') { \/\/\u8003\u8651\u60c5\u51b5\uff1ai = 9, s = \"()(()()())\"\n                if(i- dp[i-1] - 2 >= 0) dp[i] = dp[i-1] + dp[i- dp[i-1] - 2] + 2; \/\/\u628a\u4e2d\u65ad\u7684\u4e5f\u8fde\u4e0a\uff0c\u5982\u679c\u6709\u7684\u8bdd\uff0c\u6bd4\u5982\u4e0a\u9762\u6837\u4f8b\u7684\u524d\u4e24\u4e2a\u5b57\u7b26\"()\"\n                else dp[i] = dp[i-1] + 2;\n            }\n            \/\/ cout << \"dp[\" << i << \"] = \" << dp[i] << endl;\n        }\n\n        return ranges::max(dp);\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
62. \u4e0d\u540c\u8def\u5f84<\/a>\u2705<\/h2>\n\n\n\n
\u53ea\u80fd\u5f80\u5de6\u6216\u5f80\u4e0b\u8d70 \u90a3\u4e48\u4e00\u4e2a\u72b6\u6001\u5c31\u53ef\u4ee5\u4ece\u5de6\u8fb9\u683c\u5b50\u548c\u4e0a\u8fb9\u683c\u5b50\u7684\u72b6\u6001\u7ee7\u627f\u800c\u6765<\/strong><\/em><\/p>\n\n\n\n
dp\u6570\u7ec4\u542b\u4e49\uff1a\u5230\u8fbe\u4e0b\u6807\u4e3a(i,j)\u4f4d\u7f6e\u7684\u8def\u5f84\u6709dp[i][j]\u6761 \u7b2c\u4e00\u884c\u548c\u7b2c\u4e00\u5217\u7684\u8def\u5f84\u90fd\u53ea\u6709\u4e00\u6761<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    int uniquePaths(int m, int n) {\n        \/\/\u5230\u8fbe\u4e0b\u6807\u4e3a(i,j)\u4f4d\u7f6e\u7684\u8def\u5f84\u6709dp[i][j]\u6761\n        vector<vector<int>> dp(m, vector<int>(n, 0));\n\n        for(int i = 0; i < m; i++) dp[i][0] = 1;\n        for(int i = 0; i < n; i++) dp[0][i] = 1;\n\n        for(int i = 1; i < m; i++) {\n            for(int j = 1; j < n; j++) {\n                dp[i][j] = dp[i-1][j] + dp[i][j-1]; \n            }\n        }\n\n        return dp[m-1][n-1];\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
64. \u6700\u5c0f\u8def\u5f84\u548c<\/a>\u2705<\/h2>\n\n\n\n
\u601d\u8def\u548c62. \u4e0d\u540c\u8def\u5f84<\/a>\u57fa\u672c\u4e00\u81f4<\/em><\/strong><\/p>\n\n\n\n
dp\u6570\u7ec4\u542b\u4e49\uff1a\u5230\u8fbe\u4e0b\u6807\u4e3a(i,j)\u4f4d\u7f6e\u7684\u8def\u5f84\u6709dp[i][j]\u6761 \u7b2c\u4e00\u884c\u548c\u7b2c\u4e00\u5217\u7684\u8def\u5f84\u90fd\u53ea\u6709\u4e00\u6761<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    int minPathSum(vector<vector<int>>& grid) {\n        int row = grid.size();\n        int col = grid[0].size();\n        \/\/\u5230\u8fbe\u4e0b\u6807\u4e3a(i,j)\u4f4d\u7f6e\u7684\u6700\u5c0f\u8def\u5f84\u6570\u5b57\u603b\u548c\u4e3adp[i][j]\n        vector<vector<int>> dp(row, vector<int>(col, 0));\n        dp[0][0] = grid[0][0];\n        for(int i = 1; i < row; i++) dp[i][0] = grid[i][0] + dp[i-1][0];\n        for(int j = 1; j < col; j++) dp[0][j] = grid[0][j] + dp[0][j-1];\n\n        for(int i = 1; i < row; i++) {\n            for(int j = 1; j < col; j++) {\n                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; \n            }\n        }\n\n        return dp[row-1][col-1];\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
5. \u6700\u957f\u56de\u6587\u5b50\u4e32<\/a>\u274c<\/h2>\n\n\n\n
\u5fd8\u8bb0\u56de\u6587\u7684\u5b50\u4e32\u600e\u4e48\u5904\u7406\u4e86<\/strong><\/em><\/p>\n\n\n\n
DP\u6570\u7ec4\u542b\u4e49\uff1a\u8868\u793a\u533a\u95f4\u8303\u56f4[i,j]\u7684\u5b50\u4e32\u662f\u5426\u662f\u56de\u6587\u5b50\u4e32\uff0c\u5982\u679c\u662f\uff0c\u5219dp[i][j]\u4e3atrue\uff0c\u5426\u5219\u4e3afalse<\/em><\/strong><\/p>\n\n\n\n
\u904d\u5386\u987a\u5e8f\u89c1\uff1a\u4ee3\u7801\u968f\u60f3\u5f55647. \u56de\u6587\u5b50\u4e32<\/a><\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    string longestPalindrome(string s) {\n        \/\/\u8868\u793a\u533a\u95f4\u8303\u56f4[i,j]\u7684\u5b50\u4e32\u662f\u5426\u662f\u56de\u6587\u5b50\u4e32\uff0c\u5982\u679c\u662f\uff0c\u5219dp[i][j]\u4e3atrue\uff0c\u5426\u5219\u4e3afalse\n        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));\n        string res = s.substr(0, 1); \/\/\u56de\u6587\u4e32\u9ed8\u8ba4\u53d6s\u7684\u7b2c\u4e00\u4e2a\u5b57\u7b26\n        int max_len = 1;\n        for(int i = s.size(); i >= 0; i--) {\n            for(int j = i; j < s.size(); j++) { \/\/\u6839\u636edp\u6570\u7ec4\u7684\u5b9a\u4e49\uff0cj >= i\n                if(s[i] == s[j]) {\n                    if(j - i <= 1) {\n                        dp[i][j] = true;\n                        if(j - i + 1 > max_len) {\n                            max_len = j - i + 1;\n                            res = s.substr(i, j - i + 1);\n                        }\n                    } else if(dp[i+1][j-1]) { \/\/ \u4e24\u79cd\u60c5\u51b5\u53ef\u4ee5\u5408\u5e76\u5728\u4e00\u8d77\uff0c\u8fd9\u91cc\u53ea\u662f\u4e3a\u4e86\u5206\u6e05\u662f\u4e0d\u540c\u7684\u60c5\u51b5\n                        dp[i][j] = true;\n                        if(j - i + 1 > max_len) {\n                            max_len = j - i + 1;\n                            res = s.substr(i, j - i + 1);\n                        }\n                    }\n                }\n            }\n        }\n\n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
1143. \u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217<\/a>\u274c<\/h2>\n\n\n\n
\u65e0\u601d\u8def<\/em><\/strong><\/p>\n\n\n\n
dp\u6570\u7ec4\u542b\u4e49\uff1atext1\u7684[0, i-1]\u90e8\u5206\u4e0etext2\u7684[0, j-1]\u90e8\u5206\u7684\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\u4e3adp[i][j]<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    int longestCommonSubsequence(string text1, string text2) {\n        \/\/ text1\u7684[0, i-1]\u90e8\u5206\u4e0etext2\u7684[0, j-1]\u90e8\u5206\u7684\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\u4e3adp[i][j]\n        vector<vector<int>> dp(text1.size()+1, vector<int>(text2.size()+1, 0));\n        int res = 0;\n        for(int i = 1; i <= text1.size(); i++) {\n            for(int j = 1; j <= text2.size(); j++) {\n                if(text1[i-1] == text2[j-1]) {\n                    dp[i][j] = dp[i-1][j-1] + 1;\n                } else {\n                    dp[i][j] = max(dp[i][j-1], dp[i-1][j]);\n                }\n                \/\/ cout << \"dp[\" << i << \"][\" << j << \"] = \" << dp[i][j] << endl;\n                res = max(res, dp[i][j]);\n            }\n        }\n \n        return res;\n    }\n};<\/code><\/pre>\n\n\n\n
\n\n\n\n
72. \u7f16\u8f91\u8ddd\u79bb<\/a>\u274c<\/h2>\n\n\n\n
\u6ca1\u4ec0\u4e48\u601d\u8def<\/strong><\/em><\/p>\n\n\n\n
dp\u6570\u7ec4\u542b\u4e49\uff1a\u4ee5\u4e0b\u6807i-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32word1\uff0c\u548c\u4ee5\u4e0b\u6807j-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32word2\uff0c\u6700\u8fd1\u7f16\u8f91\u8ddd\u79bb\u4e3adp[i][j]\uff08\u5373word1\u4e2d\u524di\u4e2a\u5b57\u6bcd\u7ec4\u6210\u7684\u5b57\u7b26\u4e32\uff0c\u548cword2\u4e2d\u524dj\u4e2a\u5b57\u6bcd\u7ec4\u6210\u7684\u5b57\u7b26\u4e32\uff0c\u6700\u8fd1\u7f16\u8f91\u8ddd\u79bb\u4e3adp[i][j]\uff09<\/strong><\/em><\/p>\n\n\n\n
\u5171\u56db\u79cd\u60c5\u51b5\uff1a\u65e0\u9700\u7f16\u8f91\u3001\u5220\u9664word1\u7684\u4e00\u4e2a\u5b57\u6bcd\u3001\u5220\u9664word2\u7684\u4e00\u4e2a\u5b57\u6bcd\u3001\u66ff\u6362\u4e00\u4e2a\u5b57\u6bcd<\/em><\/strong><\/p>\n\n\n\n
class Solution {\npublic:\n    int minDistance(string word1, string word2) {\n        \/\/\u4ee5\u4e0b\u6807i-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32word1\uff0c\u548c\u4ee5\u4e0b\u6807j-1\u4e3a\u7ed3\u5c3e\u7684\u5b57\u7b26\u4e32word2\uff0c\u6700\u8fd1\u7f16\u8f91\u8ddd\u79bb\u4e3adp[i][j]\n        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));\n\n        for(int i = 0; i <= word1.size(); i++) dp[i][0] = i;\n        for(int i = 0; i <= word2.size(); i++) dp[0][i] = i;\n\n        for(int i = 1; i <= word1.size(); i++) {\n            for(int j = 1; j <= word2.size(); j++) {\n                if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];\n                else dp[i][j] = min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]}) + 1;    \n            }\n        }\n\n        return dp[word1.size()][word2.size()];\n    }\n};<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
More content\uff1a\u529b\u6263\u9898\u8bb0\u4e4b\u52a8\u6001\u89c4\u5212 70. \u722c\u697c\u68af\u2705 dp\u6570\u7ec4\u4e0b\u6807\u4ee3\u8868\u5f53\u524d\u5728\u7b2c\u51e0\u9636\uff0c\u6570\u7ec4value\u8868 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[27,18,19,61],"class_list":["post-1744","post","type-post","status-publish","format-standard","hentry","category-suanfa","tag-c","tag-leetcode","tag-19","tag-61"],"_links":{"self":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/1744","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1744"}],"version-history":[{"count":26,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/1744\/revisions"}],"predecessor-version":[{"id":2786,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/1744\/revisions\/2786"}],"wp:attachment":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1744"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1744"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1744"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}