leetcode演算法之動態規劃（二）

• 2021 年 2 月 11 日
• AI
• C/C++/C#

今天來盤一盤 **動態規劃 ** 這類題目

這是最讓我頭疼的一類題目，一直不想做這類題目，這裡開始學習一下。

使用python刷題分類整理的筆記,請參考: //github.com/lxztju/leetcode-algorithm/tree/v1

動態規劃

動規就是以空間換取時間。

動態規劃常常適用於有重疊子問題和最優子結構性質的問題。

一些思考的套路： 遞歸 （自頂向下）——> 記憶化遞歸（自頂向下消除重複） ——> 動態規劃（自底而上）

3. 數組區間

• 303 區域和檢索 – 數組不可變（easy）
• 413 等差數列劃分（medium）

4. 分割整數

• 343 整數拆分（medium）
• 279 完全平方數（medium）
• 91 解碼方法（medium）

3. 數組區間

303 區域和檢索 – 數組不可變（easy）

• 直接使用dp[i][j]保存ij之間的距離, 每次需要的時候直接查找即可。

class NumArray {

private:
    vector<vector<int>> dp;
public:
    NumArray(vector<int>& nums) {
        int n = nums.size();
        dp = vector<vector<int>> (n, vector<int>(n, 0));
        for ( int  i = 0; i < n; i++){
            dp[i][i] = nums[i];
        }
        for (int i = 0; i < n-1; i++){
            for (int j = i+1; j < n; j++){
                dp[i][j] = dp[i][j-1] + nums[j];
            }
        }
    }
    
    int sumRange(int i, int j) {
        return dp[i][j];
    }
};

• 也可以使用dp[i]保存起始位置到i的序列和
• ij之間的距離採用dp[j] – dp[i]得到

class NumArray {

private:
    vector<int> dp;
public:
    NumArray(vector<int>& nums) {
        int n = nums.size();
        dp =  vector<int>(n, 0);
        if ( n > 0){
            dp[0] = nums[0];
            for ( int  i = 1; i < n; i++){
                dp[i] = dp[i-1] + nums[i];
            }
        }
    }
    
    int sumRange(int i, int j) {
        if (i == 0) return dp[j];
        return dp[j] - dp[i - 1];
    }
};

413 等差數列劃分（medium）

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        vector<int> dp(A.size(), 0);
        int res = 0;
        for (int i = 2; i< A.size(); i++){
            if (A[i] + A[i-2] == 2 * A[i-1]){
                dp[i] = dp[i-1] + 1;
                res += dp[i];
            }
        }
        return res;
    }
};

4. 分割整數

343 整數拆分（medium）

• dp[i]表示i拆分後的最值， dp[i]可以拆分為j, i-j， 那麼i-j可以選擇繼續拆分與否，取最值
• 為什麼不考慮j是否拆分呢，考慮遞歸樹即可想明白。
• 考慮一棵直觀的遞歸樹。 求dp[n]， 可以分為1dp[n-1],或者2 dp[n-2] …… (n-1) * dp[1]。

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 1);
        dp[0] = 0;
        for (int i = 2; i< n+1; i++){
            for (int j = 1; j < i; j++){
                dp[i] = max(dp[i], max(j * dp[i - j], j * (i-j)));
            }
        }
        return dp[n];
    }
};

279 完全平方數（medium）

• dp[i]表示i為結尾的完全平方數
• i分為j與i – jj， 那麼dp[i] = dp[i-jj] + 1

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1, INT_MAX);
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i< n+1; i++){
            int tmp = sqrt(i);
            for (int j = 1; j < tmp + 1; j++){
                dp[i] = min(dp[i], dp[i - j * j] + 1 );
            }
            // cout<<dp[i]<<endl;
        }
        return dp[n];
    }
};

91 解碼方法（medium）

• dp[i]表示從開始到i為止的解碼方案
• 分為如下的三種情況：
  • 1. s[i]== ‘0’ 那麼這個字元只能與前邊的匹 配 dp[i] = dp[i-2]
  • 2. s[i] != ‘0’ && 能與前邊字元匹配 dp[i] = dp[i-1] + dp[i-2]
  • 3. s[i] != ‘0’ 並且不能與前置字元匹配 dp[i] = dp[i-1]

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        vector<int> dp(n+1, 0);
        if (n == 0) return 0;
        if (s[0] - '0' == 0) return 0;
        dp[0] = 1;
        dp[1] = s[0] != '0' ? 1 : 0;
        for (int i = 1; i < s.size(); i++){

            if (patch(s, i) && s[i] == '0')
                dp[i + 1] = dp[i-1];
            else if (s[i] != '0' && patch(s, i))
                dp[i+1] = dp[i] + dp[i-1];
            else if (s[i] != '0' && ! patch(s, i))
                dp[i+1] = dp[i];
        }

        return dp[n];
    }
    bool patch(string& s, int i){
        int tmp1 = s[i-1] - '0';
        int tmp2 = tmp1 * 10 + s[i] - '0';
        if (tmp2 >=10 && tmp2 <= 26)
            return true;
        return false;
    }
};

更多分類刷題資料

• 微信公眾號： 小哲AI

  

• GitHub地址： //github.com/lxztju/leetcode-algorithm

• csdn部落格： //blog.csdn.net/lxztju

• 知乎專欄： //www.zhihu.com/column/c_1101089619118026752

• AI研習社專欄：//www.yanxishe.com/column/109