算法：動态規劃（二）

- 分割字元串

給你一個字元串 s，請你将 s 分割成一些子串，使每個子串都是 回文串 。傳回 s 所有可能的分割方案。

回文串 是正着讀和反着讀都一樣的字元串。

class Solution {
private:
    vector<string> tempanswer;
    vector<vector<string>> result;

public:
    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<bool>>isTenetdp(n, vector<bool>(n, false));
        vector<vector<int>>dp(n, vector<int>(n, 0));
        for(int i = 0; i < n; i++){
            isTenetdp[i][i] = true;
            dp[i][i] = 1;
            if(i < n - 1 && s[i] == s[i + 1])
                isTenetdp[i][i + 1] = true;
        }

    }

    
};
           

經驗：

1、第一次審題的時候出現了誤差，以為是傳回所有的分割方法數

2、DFS+DP的想法很獨特，确實如果要傳回所有的分割方法的話确實是應該使用DFS，而DP主要是為了降低判斷回文串的時間複雜度 。

- 單詞拆分

給定一個非空字元串 s 和一個包含非空單詞的清單 wordDict，判定 s 是否可以被空格拆分為一個或多個在字典中出現的單詞。

說明：

拆分時可以重複使用字典中的單詞。

你可以假設字典中沒有重複的單詞。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int length = s.size();
        vector<bool>dp(length + 1, false);
        dp[0] = true;
            
        for(int i = 1; i  <= length; i++){
            for(int j = 0; j <= i; j++){
                if(dp[j] && isSplited(s.substr(j, i - j), wordDict)){
                    dp[i] = true;
                    break;
                }
            }                 
        } 
        return dp[length];
    }

    bool isSplited(string s, vector<string>& wordDict){
        int n = wordDict.size();
        for(int i = 0; i < n; i++)
            if(wordDict[i] == s)
                return true;
        return false;
    }
};
           

經驗：

1、又是DP三分鐘，調邊界一年的問題

2、注意Python的嵌套條件語句習慣請不要帶到C++裡，說多了都是淚。。習慣所有控制語句都加上括号應該可以有效避免這個問題，雖然看上去代碼行數可能會變長。

• 乘積最大子數組

給你一個整數數組 nums ，請你找出數組中乘積最大的連續子數組（該子數組中至少包含一個數字），并傳回該子數組所對應的乘積。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        vector<vector<long>>dp(n, vector<long>(2));
        for(int i = 0; i < n; i++){
            dp[i][0] = dp[i][1] = nums[i];
        }

        for(int i = 1; i < n; i++){
            long temp = nums[i];
            long a = temp * dp[i - 1][0];
            long b = temp * dp[i - 1][1];
            dp[i][0] = max(a, max(b, temp));
            dp[i][1] = min(a, min(b, temp));
        }

        long result = LONG_MIN;
        for(int i = 0; i < n; i++)
            if(dp[i][0] > result)
                result = dp[i][0];
        return result;
    }

};
           

經驗：

1、第一次寫出這種shape是<n, 2>的DP題，值得紀念。

2、algorithm包中的max函數隻能比較同樣類型的數。不能int和long互相比。

3、最大值

T Max(T x, T y, T z)
{
	return x > y ? (x > z ? x : z) : (y > z ? y : z);
}
           

- 打家劫舍

你是一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ，一夜之内能夠偷竊到的最高金額。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1)
            return nums[0];
        else if(n == 0)
            return 0;
        else if(n == 2)
            return max(nums[0], nums[1]);
        
        vector<int>dp(n);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < n; i++){
            dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
        }
        return dp[n - 1];
    }
};
           

經驗：

1、水題，雖然最開始錯誤了解成了是奇數和偶數

- 打家劫舍 II

你是一個專業的小偷，計劃偷竊沿街的房屋，每間房内都藏有一定的現金。這個地方所有的房屋都 圍成一圈 ，這意味着第一個房屋和最後一個房屋是緊挨着的。同時，相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警 。

給定一個代表每個房屋存放金額的非負整數數組，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1)
            return nums[0];
        vector<int>a(n);
        vector<int>b(n);
        for(int i = 0; i < n - 1; i++){
            a[i] = nums[i];
            b[i] = nums[i + 1];
        }
            
        return max(rob_origin(a), rob_origin(b));
    }

    int rob_origin(vector<int>& nums) {
        int n = nums.size();
        if(n == 1)
            return nums[0];
        else if(n == 0)
            return 0;
        else if(n == 2)
            return max(nums[0], nums[1]);
        
        vector<int>dp(n);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < n; i++){
            dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
        }
        return dp[n - 1];
    }
};
           

經驗：

1、給想複雜了，，<n, 2>的DP上頭了然後一直沒有想到直接拆成兩種不同的數列分别求一遍然後取大的那個即可。。