T1:一個數(shù)組 中的最長 升序 子序列 的長度

給你一個整數(shù)數(shù)組?nums?，找到其中最長嚴格遞增子序列的長度。

子序列?是由數(shù)組派生而來的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7]?是數(shù)組?[0,3,1,6,2,2,7]?的子序列。

解：

1.關(guān)鍵

（1）這是一個 非常經(jīng)典的 動態(tài)規(guī)劃的 題目， 就是 智工學院的上課的 那個例題

(2)利用 一個 數(shù)組 len[i] 記錄 原來vec中以vec[i] 元素 作為結(jié)束的 子序列的長度

(3)從前往后更新， 初始條件 len[0] = 1;在計算len[i] 的時候 ，遍歷一次 nums[0]到nums[i-1]如果有nums[j] < nums[i] 那個 max的長度 可以是 len[j]+1,實在沒有就設(shè)置為1

2.代碼：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        //找出 最長的嚴格上升 子序列的 長度 
        //利用 動態(tài)規(guī)劃的 轉(zhuǎn)移方程：只要遍歷依次即可
        //len[i]代表 以nums數(shù)組中第i個元素結(jié)束的 所有子序列中 最長的長度
        //轉(zhuǎn)移方程： len[0]-len[i-1]中的如果有nums[0]-nums[i-1] < nums[i]的最長的+1
        
        //實在沒有，就設(shè)置為1 ， 這個就是 遞推關(guān)系 方程（轉(zhuǎn)移方程）

        int size = nums.size();
        vector<int> len(size,0);
        len[0] = 1;
        for(int i=1;i<size;i++)
        {
            //--
            int max = 1;
            for(int j=0;j<=i-1;j++)
            {
                if(nums[j] < nums[i])
                {
                    int tmp =len[j];
                    if(len[j] +1 > max)
                    {
                        max =len[j]+1;
                    }
                }
            }
            len[i] = max;
        }
        //--遍歷依次 len數(shù)組即可
        int max = len[0];
        for(int i=1;i<size;i++)
        {
            if(len[i] > max)
            {
                max = len[i];
            }
        }
        return max;
    }
};

T2:（上一題的 拓展）最長 遞增子序列的 個數(shù)

給定一個未排序的整數(shù)數(shù)組?nums?，?返回最長遞增子序列的個數(shù)?。

注意?這個數(shù)列必須是?嚴格?遞增的。

解：

1.關(guān)鍵：

（1）上一問 利用的是vector<int> len，用len[i]來存儲 以對應(yīng) 位置元素作為結(jié)尾的 遞增子序列的 最大長度

（2）這里考慮 使用 vector<pair<int,int>> len, len[i].first 用來存儲以第i個元素作為結(jié)尾的 遞增子序列的最大長度， len[i].second用來存儲 這樣的 子序列的 個數(shù)

(3） 最重要的 就是 轉(zhuǎn)移方程中 是cnt+=len[j].second 或者 cnt = len[j].second ，不是+1！

2.代碼：

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        //沒有區(qū)別，反正就是最后 遍歷的那一步改一下即可
        int size = nums.size();
        vector<pair<int,int>> len(size,make_pair(0,0));
        len[0] = make_pair(1,1); //以第0個元素結(jié)尾的遞增子序列最大長度為1，且這種序列有1個
        int max_all= 1;

        for(int i=1;i<size;i++)
        {
            int max=1;
            int time =1; //max出現(xiàn)的次數(shù)
            //int max_add = 0;
            for(int j=0;j<=i-1;j++)
            {
                if(nums[j] < nums[i])
                {
                    //進入這里說明 len[i]>=2
                    //雖然，可能max == max_all ，但是這個結(jié)尾可能有 多個！
                    if(len[j].first +1== max)
                    {
                        time+=len[j].second; //加上 第j個下標為止的 出現(xiàn)次數(shù)?。?！
                    }
                    else if(len[j].first+1 > max)
                    {
                        max= len[j].first+1;
                        time=len[j].second; //重新計數(shù)
                    }
                    
                }
            }
            len[i] = make_pair(max,time); //這個是 以nums[i]結(jié)尾的 最長的子序列的長度 和 出現(xiàn)的次數(shù)
            if(max > max_all)
            {
                //cout<<"竟然沒來過》"<<endl;
                max_all = max;
            }
        }
        //特殊：
        if(max_all == 1)
        {
            //cout<<"來過嗎"<<endl;
            return size; //所有都是
        }
        //遍歷一次
        int ans = 0;
        for(auto [v1,time1]:len)
        {
            if(v1 == max_all)
            {
                ans+=time1;
            }
        }
        return ans;
        //悟：原來 可能會有可能是 相同的 終點
        //所以： 不用len數(shù)組進行記錄 終點， 而是 記錄當前遍歷過的 長度為 “當前max”的子序列個數(shù)
        //遍歷len數(shù)組
    }
};

T3：俄羅斯套娃 信封問題

給你一個二維整數(shù)數(shù)組 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 個信封的寬度和高度。

當另一個信封的寬度和高度都比這個信封大的時候，這個信封就可以放進另一個信封里，如同俄羅斯套娃一樣。

請計算 最多能有多少個 信封能組成一組“俄羅斯套娃”信封（即可以把一個信封放到另一個信封里面）。

注意：不允許旋轉(zhuǎn)信封。

解：

法一：考慮使用 歸并排序（以第一個數(shù)據(jù)的大小為基準） + 一般的 最大遞增子序列

1.關(guān)鍵：

（1）熟練遞歸函數(shù)的寫法：merge_sort函數(shù)是一個遞歸函數(shù)，一直遞歸到 只有0個或者1個元素為止,然后遞歸調(diào)用merge_sort,最后將有序的left 和 right 傳遞給merge返回一個排序好的? ?、 merge函數(shù)是一個普通的迭代函數(shù)，通過把 2個有序的線性表 left 和 right 合并為一個有序的 線性表 ans即可

(2)最大遞增子序列的 寫法見上

2.代碼：

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        //這個題目 和 最大遞增子序列 如出一轍,幾乎沒有區(qū)別
        //(1)算了， 先寫一個 歸并排序，好了，就按照第一個 元素的大小 進行排序
        merge_sort(envelopes);
        //好吧。當我沒說 ， 應(yīng)為這一題需要考慮順序， 所以可以先排序！
        int max_all =1;
        int size = envelopes.size();
        vector<int> len(size,0);
        len[0] = 1;
        for(int i=1;i<size;i++)
        {
            int max = 1;
            for(int j=0;j<=i-1;j++)
            {
                if(envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1])
                {
                    //可以加1了
                    if(len[j] + 1 > max)
                    {
                        max = len[j] +1;
                    }
                }
            }
            len[i] = max;
            if(max > max_all)
            {
                max_all = max;
            }
        }
        //show(len);
        return max_all;
    }
    //--merge_sort函數(shù)
    void merge_sort(vector<vector<int>>& envelopes)
    {//這是一個遞歸函數(shù)，先不斷分成 1個元素 或者 0 個元素，然后將 有序的 left 和 right傳給
    //merge函數(shù)進行合并
        int size = envelopes.size();
        //(1)出口
        if(size ==0 || size == 1)
        {
            return ;
        }
        //(2)先 一直二分 到 只剩1個或者 0個元素為止
        int size_left = size/2;
        int size_right = size-size_left; //右邊數(shù)組的 大小
        vector<vector<int>> left(envelopes.begin(),envelopes.begin()+size_left); //應(yīng)該是 左閉右開--測試一下 √
        vector<vector<int>> right(envelopes.begin()+size_left,envelopes.end());
        //(3)分別對 left 和 right調(diào)用2次 merge_sort
        merge_sort(left);
        merge_sort(right);
        //(4)現(xiàn)在得到的 left 和 right都是 有序的了
        //可以merge了
        envelopes = merge(left,right);
        
    }
    vector<vector<int>> merge(vector<vector<int>> left,vector<vector<int>> right)
    {
        //(1)左右 2個數(shù)組都是有序的
        int size1 = left.size();
        int size2 = right.size();
        if(size1 == 0)
        {
            return right;
        }
        if(size2 == 0)
        {
            return left;
        }
        //(2)進行循環(huán) 合并
        int i=0, j=0;
        vector<vector<int>> ans;
        while(i<size1 && j <size2)
        {
            //讓第一個元素 小的 先加入到 ans中
            if(left[i][0] < right[j][0])
            {
                ans.push_back(left[i]);
                i++;
            }
            else 
            {
                ans.push_back(right[j]);
                j++;
            }
        }
        //(3)收尾
        while(i<size1)
        {
            ans.push_back(left[i++]);
        }
        while(j<size2)
        {
            ans.push_back(right[j++]);
        }
        return ans; //這是一個 合并好的 有序 數(shù)組
    }
};

可惜， 這種方式有2個測試用例超時了，只能 另謀出路

法二：二分 -- 這里抄答案了。。。

class Solution {
private:
    struct node {
        int w, h;
        node(): w(0), h(0) {}
        node(int x, int y): w(x), h(y) {}
    };
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int len=envelopes.size();
        if(len==0) return 0;
        vector<node> arr;
        for(auto &a:envelopes) arr.push_back(node(a[0],a[1]));
        sort(arr.begin(), arr.end(), [](node x, node y){return x.w>y.w || (x.w==y.w && x.h<y.h);});
        vector<int> res(1,arr[0].h);
        int j=0;
        for(int i=1; i<len; i++) {
            if(arr[i].h<res.back()) res.push_back(arr[i].h);
            else {
                j=lower_bound(res.begin(), res.end(), arr[i].h, greater<int>())-res.begin();
                res[j]=arr[i].h;
            }
        }
        return res.size();
    }
};

T4:最大 連續(xù) 子序列的和

給你一個整數(shù)數(shù)組?nums?，請你找出一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

子數(shù)組?是數(shù)組中的一個連續(xù)部分。

解：

1.關(guān)鍵：

（1）遞推關(guān)系： dp[i] = max(dp[i-1] + nums[i] , nums[i] )?

? ? ? ? ?初值：? ? ? ? dp[0] = nums[0]

2.代碼：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //連續(xù)的 最大子序 和 
        //遞推關(guān)系：dp[i] = max(dp[i-1] , dp[i-1] + nums[i])
        //初值：dp[0] = nums[0]
        int size= nums.size();
        vector<int> dp(size,0);
        dp[0] = nums[0];
        int max_num =dp[0];
        for(int i=1;i<size;i++)
        {
            dp[i] = max(nums[i], dp[i-1] + nums[i]);
            if(dp[i] > max_num)
            {
                max_num = dp[i];
            }
        }
        return max_num;
    }
};

T5:乘積最大 連續(xù)子數(shù)組

給你一個整數(shù)數(shù)組 nums?，請你找出數(shù)組中乘積最大的非空連續(xù)子數(shù)組（該子數(shù)組中至少包含一個數(shù)字），并返回該子數(shù)組所對應(yīng)的乘積。

測試用例的答案是一個?32-位 整數(shù)。

子數(shù)組 是數(shù)組的連續(xù)子序列。

解：

1.關(guān)鍵：

（1）雖然思路 和 上面這個求和的題目是一樣的，但是 要考慮 “負數(shù)”的影響

(2)創(chuàng)新想法：考慮使用dp1[i] 存儲以第i個元素結(jié)束的最大連續(xù)乘積?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 使用dp2[2]存儲以第i個元素結(jié)束的最小連續(xù)乘積

(3)修改后的 遞推關(guān)系（狀態(tài)轉(zhuǎn)移方程）:

dp1[i]?=?max(nums[i],nums[i]*dp1[i-1]?,nums[i]*dp2[i-1]);

????????//?????dp2[i]?=?min(nums[i],nums[i]*dp1[i-1],nums[i]*dp2[i-1]);

2.代碼：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        //哎，先嘗試一下是否可以利用 “求和”一樣的想法
        //果然不行，因為，你想，可能dp[i-2] < 0 ,但是 nums[i-1] >0 而nums[i] <0
        //建議保留 最大數(shù) 和 最小的數(shù)我覺得可以 ，分別用dp1 和 dp2 兩個數(shù)組進行存儲
        //然后 dp1[i] = max(nums[i],nums[i]*dp1[i-1] ,nums[i]*dp2[i-1]);
        //     dp2[i] = min(nums[i],nums[i]*dp1[i-1],nums[i]*dp2[i-1]);
        //最后返回 max_num1即可
        int max_num = nums[0];
        int min_num = nums[0];
        int size = nums.size();
        vector<int> dp1(size,0);
        vector<int> dp2(size,0);
        dp1[0] = nums[0] ; //初值
        dp2[0] = nums[0] ;

        for(int i=1;i<size;i++)
        {
            dp1[i] = max_3(nums[i] , dp1[i-1]*nums[i],dp2[i-1]*nums[i]);
            dp2[i] = min_3(nums[i] , dp1[i-1]*nums[i],dp2[i-1]*nums[i]);
            if(dp1[i] > max_num)
            {
                max_num = dp1[i];
            }
        }
        return max_num;
    }

    //--自己寫2個3元max 和 3元min的函數(shù)
    int max_3(int a,int b, int c)
    {
        if(a>b && a>c)
        {
            return a;
        }
        else if(b>c)
        {
            return b;
        }
        return c;
    }
    int min_3(int a,int b,int c)
    {
        if(a<b && a<c)
        {
            return a;
        }
        else if(b<c)
        {
            return b;
        }
        return c;
    }
};

T6:環(huán)形連續(xù)子數(shù)組的 最大和

給定一個長度為 n 的環(huán)形整數(shù)數(shù)組?nums?，返回?nums?的非空 子數(shù)組 的最大可能和?。

環(huán)形數(shù)組?意味著數(shù)組的末端將會與開頭相連呈環(huán)狀。形式上， nums[i] 的下一個元素是 nums[(i + 1) % n] ， nums[i]?的前一個元素是 nums[(i - 1 + n) % n] 。

子數(shù)組 最多只能包含固定緩沖區(qū)?nums?中的每個元素一次。形式上，對于子數(shù)組?nums[i], nums[i + 1], ..., nums[j]?，不存在?i <= k1, k2 <= j?其中?k1 % n == k2 % n?。

解：

法一：（3個測試用例超時）最樸素的想法，以0-n-1的下標分別作為起點，然后從這n中case中取出最大值即可

1.關(guān)鍵：

（1）外層變量i，從0到size-1,表示以第i個下標作為起點 ， 轉(zhuǎn)換到“非環(huán)形數(shù)組”的情況

(2)內(nèi)層進行 % 取模運算之后就 簡單了

(3)特別注意：為了防止出現(xiàn)負數(shù)的取模運算，我們格外+size?。。?/p>

2.代碼:

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        //這個就是 連續(xù)子數(shù)組的 最大連續(xù)和 的環(huán)形數(shù)組變形題目
        //主要是 起點的問題啊
        int size = nums.size();
        //最樸素的 想法就是 ： 分size個不同的起點 進行討論， 然后其最大值
        //那就先按照這種想法進行求解好了
        //假設(shè)某一次 從起點 下標i開始
        int max1 = nums[0];
        for(int i=0;i<=size-1;i++)
        {
            //遞增的dp[j%size] , 就可以了 ,nice
            //
            vector<int> dp(size,0);
            dp[i%size]=nums[i%size];
            int max2 = nums[i%size]; //初值設(shè)置好，然后可以進行 遞推了
            for(int j=(i+1)%size; (j%size)!=i%size; j++)
            {
                dp[j%size] = max(dp[(j-1+size)%size]+nums[j%size] , nums[j%size]);
                //哦，原來是這個地方，“負數(shù)”進行模運算，一定要轉(zhuǎn)換為 整數(shù)進行模運算！??！
                if(dp[j%size] > max2)
                {
                    max2 = dp[j%size];
                }
            }
            if(max2 > max1)
            {
                max1 = max2;
            }
        }
        return max1;
    }
};

法二：借鑒 題解的那個想法（圖解 很美妙）-- 將 “環(huán)形數(shù)組”的連續(xù)和 分為 收尾不接 和 收尾相接

1.關(guān)鍵：

（1）總共2中情況，第一種，就是一般的 連續(xù)子數(shù)組的最大和 ， 第二種，就是用 數(shù)組中元素的總和? -（減去）連續(xù)子數(shù)組的最小和?

(2)不過呢，有一個小坑，就是求min_num最小連續(xù)子數(shù)組的和的 時候，最好從下標1開始計算，直接忽略下標0開始的case，因為這樣可以防止min_num和total_sum都取了整個數(shù)組之和，反正min_num少考慮的情況在max_num中其實已經(jīng)考慮過了

2.代碼：

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {

        //那個 國外的題解的 圖形化講解 非常到位
        //環(huán)形：2中case ，收尾不接 和 收尾相接
        //而根據(jù) 圖形中的描述，收尾相接其實 就是 數(shù)組總和 - 收尾不接的min連續(xù)和
        //分別計算 min 和 max 的數(shù)組連續(xù)和
        int size = nums.size();
        //特殊：
        if(size == 1)
        {
            return nums[0];
        }
        vector<int> dp1(size,0); //求max
        vector<int> dp2(size,0); //求min
        dp1[0] = nums[0]; dp2[1] = nums[1]; //設(shè)置初值
        int max_num = nums[0];
        int min_num = nums[1];
        int total_sum = nums[0];

        for(int i=1;i<size;i++)
        {
            //(1)求總和:
            total_sum += nums[i];
            //(2)遞推
            dp1[i] = max(nums[i] , nums[i] + dp1[i-1]);
            if(dp1[i] > max_num)
            {
                max_num = dp1[i];
            }
            if(i > 1)
            {
                dp2[i] = min(nums[i] , nums[i] + dp2[i-1]);
                if(dp2[i] < min_num)
                {
                    min_num = dp2[i];
                }
            }
        }
        //不能為空集對吧，那簡單，只要 min_num連續(xù)和 是從下標1開始計算的就好了
        int ans = max(max_num , total_sum - min_num);
        return ans;
    }
};

T7: 最大子矩陣和?

給定一個正整數(shù)、負整數(shù)和 0 組成的 N × M?矩陣，編寫代碼找出元素總和最大的子矩陣。

返回一個數(shù)組?[r1, c1, r2, c2]，其中?r1,?c1?分別代表子矩陣左上角的行號和列號，r2,?c2?分別代表右下角的行號和列號。若有多個滿足條件的子矩陣，返回任意一個均可。

注意：本題相對書上原題稍作改動

解：

第一次代碼：（雖然有2個測試用例超時了）

1.關(guān)鍵：

（1）核心思想： “降維”，將二維降至一維的case，通過一個2層循環(huán)，得到從第i行到第j行的每一列之和 作為 一維數(shù)組base數(shù)組的對應(yīng)列的數(shù)值 ， 然后對base數(shù)組用 一維最大連續(xù)子數(shù)組的方法進行求和

2.第一次代碼：

class Solution {
public:
    vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
        //借鑒了討論區(qū)的 思路后，自己重新思考一遍
        //(1)核心思想：“降維”--將二維的問題轉(zhuǎn)化為 一維的問題
        //設(shè)置一個一維數(shù)組base,然后通過2層循環(huán)遍歷:第i行 到第j行 中第k列之和存到base[k]中
        //然后 對base數(shù)組 使用 一維數(shù)組 最大子數(shù)組連續(xù)和的 思路即可
        //好吧，還是有2給測試用例超時了，應(yīng)該少用一個循環(huán)的
        int size_i = matrix.size();
        int size_j = matrix[0].size();
        //特殊:
        int max_all = matrix[0][0];
        vector<int> ans(4,0);
        //vector<int> base(size_j , 0);
        for(int i=0;i<=size_i - 1;i++)
        {
            for(int j=i;j<=size_i - 1;j++) 
            {
                vector<int> base(size_j , 0); //忘記置0了
                //從第i行到 第j行之和
                for(int k=0;k<=size_j-1;k++)
                {
                    for(int u=i;u<=j;u++)
                    {
                        base[k]+=matrix[u][k];
                    }
                }
                //好了，現(xiàn)在得到了base數(shù)組了,然后利用 一個子函數(shù) ，得到max
                vector<int> index(2,0);
                int max_sum = max_vec(base,index); //還要起點 和 終點
                //記錄 左上角 和 右下角
                //左上角（i,index[0]） 右下角 (j,index[1])
                if(max_sum > max_all)
                {
                    max_all = max_sum;
                    ans[0] = i;
                    ans[1] = index[0];
                    ans[2] = j;
                    ans[3] = index[1];
                }
            }
        }
        return ans;
    }
    //--一維數(shù)組 最大連續(xù)子數(shù)組的 和
    int max_vec(vector<int> nums ,vector<int>& index)
    {
        //--
        int dp_i=nums[0];
        int max_sum = nums[0];
        int size = nums.size();
        int begin = 0;
        int end = 0;
        
        for(int i=1;i<size;i++)
        {
            if(dp_i + nums[i] < nums[i])
            {
                //自立門戶
                dp_i = nums[i];
                begin = i;
            }
            else
            {
                dp_i = nums[i] + dp_i;
            }
            if(dp_i > max_sum)
            {
                max_sum = dp_i;
                //記錄起點 和 終點
                index[0] = begin;
                index[1] = i;
            }
        }
        return max_sum;
    }
};

修改后代碼：

class Solution {
public:
    vector<int> getMaxMatrix(vector<vector<int>>& matrix) {
        //這一波借鑒了討論區(qū)的想法之后，悟了
        int size_i = matrix.size();
        int size_j = matrix[0].size();

        int dp_i =matrix[0][0];
        int max_all =matrix[0][0];
        vector<int> ans(4,0); //用于記錄左上角 和 右下角的 坐標
        int left_1 = 0; //記錄左上角
        int left_2 = 0;
        //3層循環(huán)
        for(int i=0;i<=size_i-1;i++)
        {
            vector<int> base(size_j,0); //初始話base數(shù)組
            for(int j=i;j<=size_i-1;j++)
            {
                dp_i = 0;
                //一層的求和,從上往下進行求和
                for(int k=0;k<=size_j-1;k++)
                {
                    base[k]+=matrix[j][k];
                    //現(xiàn)在base就是 原來一維數(shù)組中的nums
                    //然后 與dp_i 進行比較
                    if(dp_i > 0)
                    {
                        //求和
                        dp_i += base[k];
                    }
                    else
                    {
                        //自立門戶
                        dp_i = base[k];
                        //記錄左上角
                        left_1 = i;
                        left_2 = k;
                    }
                    if(dp_i > max_all)
                    {
                        //好了，確定了全局最大值了
                        max_all = dp_i;
                        ans[0] = left_1;
                        ans[1] = left_2;
                        ans[2] = j;
                        ans[3] = k; 
                    }
                }
            }
        }
        return ans;
    }
};

!!有一點值得注意，就是 在每一次探索開始時，令dp_i = 0這么做的 合理性在于 :之后的判斷中如果dp_i > 0 那么直接加， 如果dp_i <=0 ,就把dp_i“換掉，自立門戶”,OK?

T8:矩陣區(qū)域 不超過k的最大和

給你一個?m x n?的矩陣?matrix?和一個整數(shù)?k?，找出并返回矩陣內(nèi)部矩形區(qū)域的不超過?k?的最大數(shù)值和。

題目數(shù)據(jù)保證總會存在一個數(shù)值和不超過?k?的矩形區(qū)域。

解：

1.關(guān)鍵：

（1）這一題 在“降維”的操作上 和 上一題 如出一轍，但是 在內(nèi)部，是先對求出整個base一維數(shù)組，并沒有使用dp_i進行遞推，

（2）最精妙的一步，就是 利用set容器可以 求出 lower_bound(s-k)就是說，找到恰好比s-k大的那個迭代器，所以這個位置的最大不超多k的連續(xù)和就是 從前加到這個位置的和sum -(減去)那個迭代器的數(shù)值（這里有點貪婪法的味道）

（3）有一點值得注意：就是 set容器在初始化的時候 需要向其中添加一個元素0，

其實，就是說，有一個非常特殊的情況，就是求和sum-k==0的情況，這時候，即使set中之前沒有加入一個0的元素，也應(yīng)該修改ans=k才行，所以干脆先將0加入到set中

2.代碼：

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        //好了，這個題目和上一題幾乎一樣，而且更加簡單--當我沒說
        //好了，借鑒了官方的題解，這個題雖然 這“降維”這件事上和上一題一樣
        //但是，在計算dp_i這件事上，其實并沒有用到動態(tài)規(guī)劃
        //而是，利用sum求和 - lower_bound(s-k)這個轉(zhuǎn)化
        int size_i = matrix.size();
        int size_j = matrix[0].size();
        int dp_i = matrix[0][0];
        
        const int MAX_Int = 0x6ffffff;
        int max_all = -MAX_Int; //也可以使用limit.h中的INT_MIN
        //開始3層循環(huán)
        for(int i=0;i<size_i;i++)
        {
            vector<int> base(size_j ,0);
            for(int j=i;j<size_i;j++)
            {
                //先求出所有的base
                for(int k=0;k<=size_j-1;k++)
                {
                    base[k] += matrix[j][k];
                }
                //然后 利用set容器的lower_bound操作
                set<int> sum_set; //這里必須初始加入一個0的元素
                int sum=0; //從前往后遍歷的 總和
                for(auto item:base)
                {
                    sum +=item;
                    auto left_bound = sum_set.lower_bound(sum-k);
                    if(left_bound!=sum_set.end())
                    {
                        max_all = max(max_all,sum-*left_bound);
                    }
                    sum_set.insert(sum);
                }
                
            }
        }
        return max_all;
    }
};

T9:打家劫舍

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

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

解：

1.關(guān)鍵：

（1）和《離散數(shù)學》中那種 最長沒有連續(xù)0的bit串這種問題一樣， 很容易反應(yīng)到這是一道遞推關(guān)系的問題

(2)初值：dp[0] = nums[0] , dp[1] = nums[1] ,dp[2] = nums[0] + nums[2]

dp[i]的含義：以nums[i]結(jié)束的最大可能的“和”

（3）遞推關(guān)系：dp[i]=max(dp[i-2]+nums[i] , dp[i-3]+nums[i])

2.代碼：

class Solution {
public:
    int rob(vector<int>& nums) {
        
        //只要找到遞推關(guān)系 和 初值條件就 可以 KO了
        //dp[i]代表 以第nums[i]為結(jié)尾的 最大和
        //初值:dp[0] = nums[0] , dp[1] = nums[1] ，dp[2] = nums[0] + nums[2]
        //遞推關(guān)系dp[i] = max(dp[i-2]+nums[i] , dp[i-3]+nums[i])  隔1個 或者 隔2個的情況加以討論
        int size = nums.size();
        //特殊：
        if(size == 1)
        {
            return nums[0];
        }
        if(size ==2)
        {
            return max(nums[0],nums[1]);
        }
        vector<int> dp(size,0);
        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = nums[0]+nums[2];
        for(int i=3;i<=size-1;i++)
        {
            dp[i] = max(dp[i-2]+nums[i] , dp[i-3] + nums[i]); //i-3不一定成立
        }
        int ans = max(dp[size-2] , dp[size-1]);
        return ans;
    }
};

T10:打家劫舍（II）--環(huán)形數(shù)組形式

你是一個專業(yè)的小偷，計劃偷竊沿街的房屋，每間房內(nèi)都藏有一定的現(xiàn)金。這個地方所有的房屋都 圍成一圈 ，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警 。

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

解：

1.關(guān)鍵：

（1）size<=3都 只能取一個元素， 所以直接 特殊考慮就好了

(2)一般情況的話，建議 分2個case進行考慮，第一種不取nums[size-1] 第二種 不取nums[0]

然后 return max(max1,max2)

2.代碼：

class Solution {
public:
    int rob(vector<int>& nums) {
        //(1)size<=3都算特殊情況處理
        //(2)收尾只取一個的時候就和上一題一樣了
        //--
        int size = nums.size();
        if(size == 1)
        {
            return nums[0];
        }
        else if(size == 2)
        {
            return max(nums[0] , nums[1]);
        }
        else if(size == 3)
        {
            //依然只能3取1
            int tmp = max(nums[0],nums[1]);
            return max(tmp,nums[2]);
        }
        //初值:
        
        //--不取nums[size-1]
        vector<int> dp(size,0);
        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = nums[0] + nums[2];
        for(int i=3;i<=size-2;i++)
        {
            dp[i] = max(dp[i-2]+nums[i] , dp[i-3]+nums[i]);
        }
        int max1 = max(dp[size-2],dp[size-3]);
        //--不取nums[0]
        vector<int> dp2(size,0);
        dp[0] = nums[1];
        dp[1] = nums[2];
        dp[2] = nums[1] + nums[3];
        for(int i=3;i<=size-2;i++)
        {
            dp[i] = max(dp[i-2]+nums[i+1],dp[i-3]+nums[i+1]);
        }
        int max2 = max(dp[size-2],dp[size-3]);
        
        return max(max1,max2);
    }
};

T11:刪除 與 獲得 點數(shù) （打家劫舍的 變形）

給你一個整數(shù)數(shù)組?nums?，你可以對它進行一些操作。

每次操作中，選擇任意一個?nums[i]?，刪除它并獲得?nums[i]?的點數(shù)。之后，你必須刪除 所有 等于?nums[i] - 1 和 nums[i] + 1?的元素。

開始你擁有 0 個點數(shù)。返回你能通過這些操作獲得的最大點數(shù)。

解：

1.關(guān)鍵：

（1）先對nums數(shù)組進行排序，變成遞增的數(shù)組

(2)利用一個map1 記錄<val,time> 每種元素出現(xiàn)的次數(shù)

(3)為了方便處理，將map1轉(zhuǎn)移到 vec<pair<val,time>> 中

(4)map1.size() = size2 , 特殊size2 ==1 或者 size2 == 2 可以直接處理

(5)vector<int> dp(size2,0) ,注意，這里有一個skill，就是讓dp從-1開始用，等價于 dp[0] = 0;含義就是 dp[i] 對應(yīng)以第i-1個元素作為結(jié)尾的 最大搶劫數(shù)目，這樣初值條件 dp[0] ,dp[1] ,dp[2]比較好求一些

(6)遞推方程 ， 分2種情況考慮:

case1 : vec[i].first 和 前一個是鄰居

case2:vec[i].first 和 前一個不是鄰居 , 然后可以比較方便的寫出遞推方程

2.代碼：

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        //先排序 ， 然后就是有 重復的 “打家劫舍”問題！妙啊
        //只要將 一次打劫一家 改為 打劫所有nums[i]相同的家庭 即可
        //(1)排序
        sort(nums.begin(),nums.end());
        //(2)打家劫舍
        int size= nums.size();
        //特殊:
        if(size == 1)
        {
            return nums[0];
        }
        //遞推關(guān)系：
        //我認為 可以 用一個map存儲，然后
        //dp[i] = max(nums[i] + dp[i-2] , nums[i] + dp[i-3]);
        //map不好訪問，不如利用 一個大小為size的 vec<pair<val,time>> 的輔助數(shù)組進行存儲
        //利用快慢指針轉(zhuǎn)移到這個輔助數(shù)組中
        //不如先用 map存一遍 ，然后再轉(zhuǎn)移到一個vec中
        map<int,int> map1; //<val,time>
        for(auto item:nums)
        {
            map1[item]++;
        }
        int size2 = map1.size();
        vector<pair<int,int>> vec(size2 , make_pair(0,0));
        int i=0;
        for(auto [val,time]:map1)
        {
            vec[i].first = val;
            vec[i].second = time;
            i++;
        }
        //（3）利用vec容器來寫轉(zhuǎn)移方程
        //特殊:
        if(size2 == 1)
        {
            return vec[0].first * vec[0].second;
        }
        else if(size2 == 2)
        {
            if(abs(vec[0].first - vec[1].first) == 1)
            {
                return max(vec[0].first * vec[0].second , vec[1].first * vec[1].second);
            }
            else{
                return vec[0].first * vec[0].second + vec[1].first * vec[1].second;
            }
        }
        //--?? 3個元素的case先pass
        //只有當前3個元素都是 遞增1時才需要dp[3]這個值
        //算了dp從-1開始好了
        //測試[2,2,3,3,3,4] ,size2 =3
        vector<int> dp(size2+1,0);
        dp[0] = 0;
        dp[1] = vec[0].first * vec[0].second; //dp[1] =2*2 = 4
        if(abs(vec[0].first - vec[1].first) == 1)
        {
            dp[2] = vec[1].first * vec[1].second;  //dp[2] = 3*3 = 9
        }
        else{
            dp[2] = vec[0].first * vec[0].second + vec[1].first * vec[1].second;
        }
        //考慮使用一個dp[-1]=0 作為一個初值條件
        for(int i=3;i<=size2;i++)
        {
            //分情況 遞推:
            if(vec[i-1].first - vec[i-2].first == 1) //vec[0-2]可用
            {
                //好了，它們是鄰居
                dp[i] = max(vec[i-1].first*vec[i-1].second + dp[i-2] ,vec[i-1].first*vec[i-1].second + dp[i-3]); //得到dp[3] = max(4+4 , 4+ 0) = 8
            }
            else{
                //不是鄰居
                dp[i] = max(vec[i-1].first*vec[i-1].second + dp[i-1] ,vec[i-1].first*vec[i-1].second + dp[i-2]);
            }
        }
        return max(dp[size2-1],dp[size2]);

    }
};

T12:3n塊披薩

給你一個披薩，它由 3n 塊不同大小的部分組成，現(xiàn)在你和你的朋友們需要按照如下規(guī)則來分披薩：

你挑選 任意?一塊披薩。
Alice 將會挑選你所選擇的披薩逆時針方向的下一塊披薩。
Bob 將會挑選你所選擇的披薩順時針方向的下一塊披薩。
重復上述過程直到?jīng)]有披薩剩下。
每一塊披薩的大小按順時針方向由循環(huán)數(shù)組 slices?表示。

請你返回你可以獲得的披薩大小總和的最大值。

解：

1.關(guān)鍵

（1）問題轉(zhuǎn)化：這一題 等價與 從3n個數(shù)字中 選擇 n個 不相鄰的 數(shù)字之和 最大?。?！

可以反證：只要選了相鄰的2個數(shù)字，一定不符合要求

(2)dp[i][j] 二維遞推數(shù)組 ， 含義：從前i個（從1開始用）元素中選擇j個不相鄰的數(shù)值的 最大和

（3）利用dp[0][0] ==0 可以等價于 設(shè)置了一個 -1位置的 初值條件

(4)遞推關(guān)系： dp[i][j] = max(dp[i-1][j] , dp[i-2][j-1]+slices[i-1]) 結(jié)合上述含義 很容易 分析出 這個遞推關(guān)系的含義

2.代碼：

class Solution {
public:
    int maxSizeSlices(vector<int>& slices) {
        //有點像環(huán)形 “打家劫舍” ， 但又 不完全是
        //給一個長度為 3n的環(huán)形數(shù)組，其中選擇n個不相鄰的 數(shù)之和， 使得它們的和最大
        //原來使利用的 二維dp[i][j],含義從前i個元素中 選擇j個元素之和的最大值
        //這里和 那個打家劫舍II的思路一樣，考慮分取slices[0] 和 取slices[size-1]2中case
        vector<int> vec1(slices.begin()+1,slices.end());
        vector<int> vec2(slices.begin() , slices.end()-1);
        int ans1= max_cnt(vec1);
        int ans2= max_cnt(vec2);
        return max(ans1,ans2);
    }
    int max_cnt(vector<int> slices)
    {
        //返回最大值
        int size = slices.size(); //因為相比于 原來的數(shù)組少了一個元素， 
        int choose_cnt = (1+size)/3; //需要選擇的最大元素個數(shù) , 也要預留一個-1位置作為一個也不選為0
        //注意dp使有一個等價-1位置可以用的，那個位置的元素為0
        vector<vector<int>> dp(size+1 ,vector<int>(choose_cnt+1,0));
        //方正i 和 j 都是從1開始用，表示 第i個元素
        for(int i=1;i<=size;i++)
        {
            for(int j=1;j<=choose_cnt;j++)
            {
                //遞推關(guān)系
                dp[i][j] = max(dp[i-1][j] , (i-2>=0 ?dp[i-2][j-1] : 0) + slices[i-1]); //從前i-1個中 選取 j個元素 ，或者從前i-2個中選j-1個 + slice[i-1]
                //這里巧妙的利用了i-2>=0 ? dp[i-2][j-1]:0 單獨考慮了 第1個元素的情況!!!
            }
        }
        return dp[size][choose_cnt];
    }
};

T13:最長的 斐波那契子序列的 長度

如果序列?X_1, X_2, ..., X_n?滿足下列條件，就說它是?斐波那契式?的：

n >= 3
對于所有?i + 2 <= n，都有?X_i + X_{i+1} = X_{i+2}
給定一個嚴格遞增的正整數(shù)數(shù)組形成序列 arr?，找到 arr?中最長的斐波那契式的子序列的長度。如果一個不存在，返回??0 。

（回想一下，子序列是從原序列 arr?中派生出來的，它從 arr?中刪掉任意數(shù)量的元素（也可以不刪），而不改變其余元素的順序。例如，?[3, 5, 8]?是?[3, 4, 5, 6, 7, 8]?的一個子序列）

解：

1法一：（雖然只通過了29個測試用例然后就超時了）

1.關(guān)鍵：

（1）利用一個 二維數(shù)組 dp[i][j] 作為 遞推數(shù)組， 含義，以第j個元素作為倒數(shù)第二個元素 以第i個元素作為最后一個元素的 最長斐波那契子序列的 長度

(2)遞推關(guān)系 :分情況討論 k=find_it(i,j,arr) ,代表 前面可以連接的元素 下標位置，如果k==-1,說明不能連接 ，將dp[i][j] 設(shè)置為2（雖然這個2沒有什么意義）

如果k!=-1 ,那么考慮使 以第k個元素開始 “自立門戶 ”得到dp[i][j] = 3?

還是 直接連接到k的上一次 ，如果find_it(j,k,arr) != -1 可以連接， dp[i][j] = dp[j][k]+2;

(3)其中，arr是一個嚴格遞增的有序數(shù)組，查找函數(shù)find_it使用的使 二分搜索

2.代碼：

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        //條件中 有提到 元素使 嚴格遞增（互異）的
        //dp[i][j] 以第j個元素 + 第i個 元素 結(jié)尾 的 最長斐波那契子序列
        // j < i
        //從第0-j-1個元素中 找到 符合arr[i] - arr[j] 的大小的元素 arr[k]
        //然后 dp[i][j] = dp[k][m]+2(其中dp[k][m]中找到最大的那個元素即可)
        // 或者 dp[i][j] = vec[k] ,vec[k] = max(dp[k][m]) ,   0<=m<=k-1
        //利用 二分查找 dp[k][m]中的最大值
        //利用 二分查找 arr[0-j-1]中是否有符合條件的值arr[k]
        //干脆用一個 一維數(shù)組 vec[k] 存儲以第k個元素結(jié)尾的最長的斐波那契子序列
        int size = arr.size();
        vector<vector<int>> dp(size,vector<int>(size,0));
        //i==0 的那一行不用 ， 1<=i <=size-1  ,    0<=j <=i-1
        //(1)初始條件
        //vec[0] = 1
        //先算 dp[1][0]  -- 從而得到 vec[1]=2
        //再算 dp[2][0] 和 dp[2][1]   -- 從而得到 vec[2] =xxx (<=3)
        //再算 dp[3][0] 和 dp[3][1] 和 dp[3][2] -- 從而得到 vec[3] =xxx(<=4)
        vector<int> vec(size,0);
        vec[0] = 1;
        vec[1] = 2;
        int max_all= 2;
        //(2)從dp[2][j]開始遞推
        //感覺dp[i][0]都應(yīng)該 == 2
        for(int i=1;i<=size-1;i++)
        {
            dp[i][0] = 2;
        }
        for(int i=2;i<=size-1;i++)
        {
            int max_len = 2;
            for(int j=1;j<=i-1;j++)
            {
                //二分查找是否有 符合 arr[k] = arr[i] - arr[j] 的這個第k個元素
                int k = find_it(i,j,arr);
                if(k == -1)
                {
                    //沒有以 j ,i 結(jié)尾的子序列
                    dp[i][j] = 2; //長度設(shè)置為2好了
                }
                else{
                    //dp[i][j] = dp[j][k] + 2;
                        if(find_it(j,k,arr)!= -1)
                        {
                            dp[i][j] = dp[j][k]+1;
                        }
                        else{
                            dp[i][j] = 1+2;
                        }
                    //這么干還是不妥，因為 3,11,14只能構(gòu)成3 ，但是我弄成了4
                    //核心問題：到底1，3這一對可以加入與否
                    //其實 我寫的這些 都存在一個致命的問題，就是 找到以j,i結(jié)尾了
                    //但是，就是找到了k，那你怎么直到j(luò)和k也可以
                    //除非 dp[i][j] = dp[j][k]+2;
                    //現(xiàn)在還剩下1個問題，就是第1個元素和第二個元素
                    //有辦法了：直接將dp[j][k] == 2的時候單獨處理
                    //從0-k-1中去找是否有 arr[j] - arr[k]的值
                    //又是二分查找

                    if(dp[i][j] > max_len)
                    {
                        max_len = dp[i][j]; //得到最大的長度，最后賦值 給 vec[i]
                    }
                }
            }
            //遍歷查找dp[i][所有j] ,得到max 給到vec[i]
            //
            vec[i] = max_len;
            //cout<<"以"<<arr[i]<<"結(jié)尾的最大長度:"<<max_len<<endl;
            if(vec[i] > max_all)
            {
                max_all = vec[i];
            }
        }
        //從所有的vec[i]中找到最大的
        if(max_all == 2)
        {
            return 0;
        }
        return max_all;
    }
    //--二分查找目標函數(shù):
    int find_it(int i, int j ,vector<int> arr)
    {
        int k = -1; //默認k=-1表示沒有找到 , 其中  0<=k <=j-1
        int target = arr[i] - arr[j];
        //利用二分查找
        i=j-1; j =0;
        while(i >=j)
        {
            int mid = (i+j)/2;
            if(arr[mid] == target)
            {
                return mid;
            }
            else if(arr[mid] > target)
            {
                //i 太大了
                i = mid-1;
            }
            else if(arr[mid] < target)
            {
                //j 太小了
                j = mid+1;
            }
        }
        return -1;
    }
};

法二：借鑒討論區(qū)的 思想,利用一個map容器進行改進

1.關(guān)鍵：

（1）利用map1存儲 從arr[i]數(shù)值 映射到 i 下標

(2)利用map2存儲“路徑”最終以j->k結(jié)束的 最大長度 ，雖然有2個長度還沒加上，注意，這里沒有用pair，而是用的skill:j*size+k 來“唯一”的表示一個坐標點

(3)遞推關(guān)系:

if(arr[k] - arr[j] < arr[j] && map1.count(arr[k]-arr[j])) //說明這個 下標為i的點使存在的

map2[j*size+k] = map2[i*size+j] + 1;

（4）這里附帶 討論區(qū)的思路

思路

將斐波那契式的子序列中的兩個連續(xù)項 A[i], A[j] 視為單個結(jié)點 (i, j)，整個子序列是這些連續(xù)結(jié)點之間的路徑。

例如，對于斐波那契式的子序列 (A[1] = 2, A[2] = 3, A[4] = 5, A[7] = 8, A[10] = 13)，結(jié)點之間的路徑為 (1, 2) <-> (2, 4) <-> (4, 7) <-> (7, 10)。

這樣做的動機是，只有當 A[i] + A[j] == A[k] 時，兩結(jié)點 (i, j) 和 (j, k) 才是連通的，我們需要這些信息才能知道這一連通?，F(xiàn)在我們得到一個類似于 最長上升子序列 的問題。

算法

設(shè) longest[i, j] 是結(jié)束在 [i, j] 的最長路徑。那么 如果 (i, j) 和 (j, k) 是連通的， longest[j, k] = longest[i, j] + 1。

由于 i 由 A.index(A[k] - A[j]) 唯一確定，所以這是有效的：我們在 i 潛在時檢查每組 j < k，并相應(yīng)地更新 longest[j, k]。

2.代碼：

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        //悟了，借鑒討論區(qū)的方法
        //(1)先將 利用一個map存儲用數(shù)值 -> 映射到 下標i
        int size = arr.size();
        unordered_map<int,int> map1;
        for(int i=0;i<=size-1;i++)
        {
            map1[arr[i]] = i;
        }
        int ans=0;
        unordered_map<int,int> map2;
        //(2)利用另一個map2存儲以j->k作為結(jié)束點 的最長序列 長度
        for(int k=0;k<size;k++)
        {
            for(int j=0;j<k;j++)
            {
                //遞推關(guān)系
                if(arr[k] - arr[j] <arr[j] && map1.count(arr[k]-arr[j]))
                {
                    //這個元素存在:
                    //這個元素的下標為i
                    int i = map1[arr[k] - arr[j]];
                    map2[j*size+k] = map2[i*size + j]+1;//原來以i->j為結(jié)束帶你
                    //現(xiàn)在長度加1
                    //最后 總長度還要加2，因為最后2個點沒有計算
                    ans = max(ans,map2[j*size+k]+2);
                }
            }
        }
        if(ans<=2)
        {
            return 0;
        }
        return ans;
    }
};

T14:最長 等差數(shù)列

給你一個整數(shù)數(shù)組?nums，返回 nums?中最長等差子序列的長度。

回想一下，nums 的子序列是一個列表?nums[i1], nums[i2], ..., nums[ik] ，且?0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果?seq[i+1] - seq[i](?0 <= i < seq.length - 1) 的值都相同，那么序列?seq?是等差的

解：

法一：（這一題 和 上一題的 差別 主要體現(xiàn)在 元素可以重復，所以 我打算修改上一題的 map1<int ,vector<int>> 用一個vector數(shù)組存儲所有的 具有這個val值的 下標，從小到達開始存儲）

這是一個含有 調(diào)試代碼的 代碼 ， 通過了36個測試用例后 超時了，可惜

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        //不是遞增數(shù)組， 而且元素之間 也不一定使 互異的
        //不一定使 遞增的等差序列 遞減的等差序列也可以
        //我覺得 這一題 和 上一題 幾乎是一樣的 ，因為只要確定了 j->k這個終點最表，差值也就唯一確定了
        //現(xiàn)在唯一需要考慮的問題使，元素是否會重復？？ 答：會，所以上一題的 模板用不了 啊啊
        //那就修改一下，從所有重復的中 找到那個可以接上 而且最大的 那個 接上！
        //不知道m(xù)ap<int,vector<int>> 能不能用，這樣可以就可以 將一個val映射到 一組下標位置了
        //然后去找的 時候 ，一直找到j(luò)-1為止
        //開始套用上一題的 模板
        unordered_map<int,vector<int>> map1;
        int size = nums.size();
        for(int i=0;i<=size-1;i++)
        {
            map1[nums[i]].push_back(i); // 存入一組下標值
        }
        unordered_map<int,int> map2; //用于存儲以下標j->k結(jié)束的最長子序列
        int ans=0;
        //--
        for(int k=0;k<=size-1;k++)
        {
            for(int j=0;j<=k-1;j++)
            {
                //遞推：
                //(1)先看map1中有沒有 
                int diff = nums[k] - nums[j];
                int num_i = nums[j] - diff;
                if(map1.count(num_i))
                {
                    //(2)從這個數(shù)組中找 下標 <=j-1的，然后從中選出map2[i*size+j]最大的,打擂臺
                    vector<int> tmp = map1[num_i];
                    int size_tmp = tmp.size();
                    int max_index = -1;
                    int max_len = 0;
                    for(int i=0;i<=size_tmp-1;i++)
                    {
                        cout<<"diff = "<<diff<<endl;
                        cout<<"num_i = "<<num_i<<endl;
                        cout<<j<<"->"<<k<<" "<<"tmp[i] = "<<tmp[i]<<endl;
                        if(tmp[i] > j-1)
                        {
                            break;//沒有比j-1小的了，跳出
                        }
                        if(map2[tmp[i]*size+j] >= max_len)
                        {
                            //cout<<"來過嗎"<<endl; -- 沒有
                            max_len = map2[tmp[i]*size+j];
                            max_index =tmp[i];
                        }
                    }
                    //說明max_index從來沒有被更新過
                    //case1: max_index == -1
                    if(max_index == -1)
                    {
                        //沒有合適的；
                    }
                    else
                    {
                        //cout<<"來過嗎"<<endl; -- 沒有
                        map2[j*size+k] = max_len + 1;
                        ans = max(ans , map2[j*size+k] + 2);
                    }
                }
            }
        }
        if(ans <=2)
        {
            return 2;
        }
        else{
            return ans;
        }
    }
};

法二：借鑒討論區(qū)的 思路:

1.關(guān)鍵：

（1）依然使 用一個map映射 從val 到 index ，但是?。?！ 妙！ 每次都只存最后一次出現(xiàn)的 index，這一定可以保證 “最優(yōu)”?。。?/p>

（2）利用一個二維數(shù)組 dp[i][j] 表示 以i->j結(jié)尾的 最大長度

2.代碼：

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int , int> mp;
        vector<vector<int>> dp(n , vector<int>(n , 2)); //二維 遞推數(shù)組，初始長度都為2
        int ans = 0;
        for(int i = 0 ; i < n ; i++){
            for(int j = i + 1 ; j < n ; j++){
                int target = 2 * nums[i] - nums[j]; //從i 到 j的路徑
                if(mp.count(target)) dp[i][j] = dp[mp[target]][i] + 1; //遞推方程
                ans = max(ans , dp[i][j]);
            }
            mp[nums[i]] = i; //這里每次取最后一個出現(xiàn)的 val的 index ，妙?。。?！
        }

        return ans;
    }
};

T15:形成字符串的 最短路徑

對于任何字符串，我們可以通過刪除其中一些字符（也可能不刪除）來構(gòu)造該字符串的 子序列 。(例如，“ace”?是 “abcde” 的子序列，而 “aec” 不是)。

給定源字符串?source 和目標字符串?target，返回 源字符串?source?中能通過串聯(lián)形成目標字符串?target?的 子序列 的最小數(shù)量?。如果無法通過串聯(lián)源字符串中的子序列來構(gòu)造目標字符串，則返回?-1。

解：

1.關(guān)鍵：

（1）好吧，我承認，這一題 直接用 貪心的思想 就可以 得到 最優(yōu)解

(2)和動態(tài)規(guī)劃無關(guān)：從頭開始，盡可能的 讓source起到更多的作用 (貪心)，

這么做的合理性： 因為可以使用“子序列”， 所以任何其它“非貪心”的選擇 一定 可以組合成貪心的選擇，所以一定不存在 比貪心更少的 步數(shù)。

比如說：source = abcb? target = abcbaba

貪心的第一次 :可以取abc?，那就取abc好了 ,下一個取的就是b了

非貪心第一次：我偏不，我就只取ab ,下一個我可以取cb，但是這么看的話，雖然看上去第二次多取了一些，但之所以會這樣，就是因為“貪心的取法不需要在第二步取這么多了，它其實也有取cb的能力，但是第一步幫它分擔了一個c，就不需要再取c了”，

這么看的結(jié)果是，貪心一定不會比非貪心步數(shù)更多

2.代碼：

class Solution {
public:
    int shortestWay(string source, string target) {
        //既然有人用 貪心算法 解出來了，那我也用 貪心好了
        int size1= source.size();
        int size2= target.size();
        int ans = 0 ; //步數(shù)
        int cur1 = 0;
        int cur2 = 0;

        int flag = true;
        while(cur2 < size2)
        {
            flag=true;
            cur1 = 0;
            while(cur1 < size1)
            {
                if(source[cur1] == target[cur2])
                {
                    cur2++;
                    flag = false; //說明cur2有移動
                }
                cur1++;
            }
            if(flag == true)
            {
                break;
            }
            ans++;
        }
        return flag?-1:ans;
    }
};

T16:最大 整除子集

給你一個由 無重復 正整數(shù)組成的集合 nums ，請你找出并返回其中最大的整除子集 answer ，子集中每一元素對 (answer[i], answer[j]) 都應(yīng)當滿足：
answer[i] % answer[j] == 0 ，或
answer[j] % answer[i] == 0
如果存在多個有效解子集，返回其中任何一個均可。

解：

1.關(guān)鍵：

（1）集合 --子集 -- 那必然先sort排序啊

(2)最樸素的想法就是 把前面所有可能的值 全部遍歷一次（因為 “因子”這東西，真的只好用遍歷）

(3)dp[i] 一維 遞推數(shù)組： 代表以第i個元素作為 結(jié)束點的 最長 整除子集的長度

dp_vec[i]代表 對應(yīng)上述那個最長整除子集的 具體元素的一個集合 （dp_vec是一個二維數(shù)組）

2.代碼：

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        //（1）先排序，然后 就變成和 最長的 斐波那契數(shù) 那個題 有點像了
        sort(nums.begin() ,  nums.end());
        //(2)然后 ，利用2個map加以處理
        //利用數(shù)組進行存儲:
        //最樸素的方法就是 從后往前 遍歷找因子
        int size = nums.size();
        vector<int> dp(size,0);
        vector<vector<int>> dp_vec(size);
        dp[0] = 1 ;   //初值
        dp_vec[0].push_back(nums[0]);  //
        
        int max_all = 1;
        int max_index =0;
        for(int i=1;i<size;i++)
        {
            int max_len = 1;
            int from_j = -1;
            for(int j=i-1;j>=0;j--)
            {
                if(nums[i]%nums[j] == 0)
                {
                    if(dp[j] + 1 > max_len)
                    {
                        max_len = dp[j] + 1;
                        from_j = j;
                    }
                }
            }
            dp[i] = max_len;
            //將dp_vec[j]這個數(shù)組加上一個nums[i]變成dp_vec[i]
            if(from_j == -1)
            {
                dp_vec[i].push_back(nums[i]);//自立門戶
            }
            else
            {
                dp_vec[i] = dp_vec[from_j];
                dp_vec[i].push_back(nums[i]);//添加新的元素
            }
            if(dp[i] > max_all )
            {
                max_all =dp[i];
                max_index = i;
            }
        }
        return dp_vec[max_index];

    }
};

T17:最長有效括號

給你一個只包含?'('?和?')'?的字符串，找出最長有效（格式正確且連續(xù)）括號子串的長度。

解：

1.關(guān)鍵：（我采用的 利用一個一維數(shù)組dp記錄dp[i]代表以s中第i個元素結(jié)束的最長的 有效括號長度）

(1)int max_anx: 用于記錄 打擂臺中的所有dp[i] 的最大值

vector<int> dp(n,0):用于dp[i] 記錄以s中第i個元素結(jié)束的 最長有效括號 長度

(2)初值：dp[0] =0

(3)重點?。?！ 遞推關(guān)系:

case1: s[i] == '(',好了，不用看了，dp[i] 一定是0

case2:s[i] == ')' :

<1>如果 s[i-1] =='(' ,dp[i] = dp[i-2]+2,當然，如多i-2<0,就是2了

<2>否則：需要看i-dp[i-1]-1這個位置中s的字符，如果沒有 或者 為')',直接dp[i] =0

不然,dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2;

2.代碼：

class Solution {
public:
    int longestValidParentheses(string s) {
        //利用動態(tài)規(guī)劃的思想進行求解:
        int max_ans = 0;     //所有dp[i]中的最大值
        int n =s.size();
        vector<int> dp(n,0); // 動態(tài)規(guī)劃 一維dp數(shù)組,
        //--初值：dp[0] == 0
        //dp[i] 的含義：以字符串s中第i個字符結(jié)束 的最長有效括號數(shù)的 長度
        for(int i=1;i<n;i++)
        {
            //如果s[i] ==( 左括號的話，dp[i] == 0 不用管
            if(s[i] == ')')
            {
                //分情況討論:
                if(s[i-1] == '(')
                {
                    dp[i] = (i>=2?dp[i-2]:0) + 2;
                }
                else
                {
                    //看一下s[i - dp[i-1] -1 ] 是否 == (
                    //如果不是：dp[i] = 0
                    //如果是：dp[i] = dp[i-1] + dp[i-dp[i-1]-2] +2;
                    if(i-dp[i-1] -1 <0 || s[i-dp[i-1]-1]!='(')
                    {
                        dp[i] = 0;
                    }
                    else if(i - dp[i-1] -1 ==0)
                    {
                        dp[i] = dp[i-1] + 2;
                    }
                    else{
                        dp[i] = dp[i-1] + dp[i-dp[i-1] -2]+2;
                    }
                }
                if(dp[i] > max_ans)
                {
                    max_ans = dp[i];
                }
            }
        }
        //--
        return max_ans;
    }
};

T18:等差數(shù)列劃分:

如果一個數(shù)列 至少有三個元素 ，并且任意兩個相鄰元素之差相同，則稱該數(shù)列為等差數(shù)列。

例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差數(shù)列。
給你一個整數(shù)數(shù)組 nums ，返回數(shù)組 nums 中所有為等差數(shù)組的 子數(shù)組 個數(shù)。

子數(shù)組 是數(shù)組中的一個連續(xù)序列。

解：

擴展思考--如果這個 不連續(xù)的序列中的 等差數(shù)列個數(shù)呢？

答：

好吧，一開始我就沒有考慮 連續(xù) 這個條件，所以寫出了這個代碼：

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        //計算一個數(shù)組中 等差序列的  個數(shù)cnt
        //采用動態(tài)規(guī)劃的思想：dp[i]代表 以nums[i]結(jié)束的 等差數(shù)列的 個數(shù)！--不要長度
        //一個非常巧妙的數(shù)據(jù)結(jié)構(gòu) vector<map<diff,len>> dp(n+1)
        //其實，本來是沒想過要用 這個map的，本來想用一個set去代替好了，但是
        //因為有一個問題，就是如果diff這個 只有1對，len==2,那么就不能算數(shù)了，所以還是用map好了
        int n= nums.size();
        vector<unordered_map<int,int>> dp(n);
        int cnt = 0 ; //記錄等差序列的個數(shù)
        //初值:
        dp[0][0]=1; //對于第一個元素而言，它僅有的等差序列 就是它本身了，所以存一個diff映射到長度1
        //遞推關(guān)系:
        //循環(huán)for(int j=0;j<=i-1;j++) --計算diff = nums[i] - nums[j] --遞推:
        //dp[i][diff] = dp[j][diff]+1;
        //同時,if(dp[i][diff] >=3  , cnt++)
        //比如這個測試用例：1 2 3 4
        
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                int diff = nums[i] - nums[j];
                //dp[i][diff] = dp[j][diff]+1;
                //把自己 - 自己 單獨考慮好了
                if(j==i)
                {
                    dp[i][0] = dp[i][0]+1; 
                }
                //--一般情況:
                else if(dp[j][diff] == 0)
                {
                    dp[i][diff] +=2; //第一次加入2個元素
                }
                else{
                    dp[i][diff] = dp[j][diff]+1;
                }
                if(dp[i][diff] >= 3 )
                {
                    cnt+= (dp[i][diff]-2);
                }
            }
        }
        show(dp);
        return cnt;
    }
    //有2個問題:
    //第一：測試的i==2 的時候 diff == 1 的cnt應(yīng)該要等于3才對，但是結(jié)果cnt==2
    //這個問題的核心：就是 自己 減 自己 ==0 ，但是只是產(chǎn)生1個元素
    //第二：忘記后綴形式的情況了，比如1 2 3 4中，還可以取到 2 3 4 這種后綴
    //所以：只要 cnt = k,那么總共可以產(chǎn)生k-2中可能的等差序列
    //第三：忘記了一個問題：這個題目 需要“連續(xù)的數(shù)組”
    //輔助測試函數(shù):
    void show(vector<unordered_map<int,int>> vec)
    {
        int i=0;
        for(auto map1:vec)
        {
            cout<<i++<<" :"<<endl;
            for(auto [diff,cnt]:map1)
            {
                //cout<<"diff = "<<diff<<" cnt= "<cnt;
                cout<<"diff - ";
                cout<<diff;
                cout<<" cnt -";
                cout<<cnt;

                cout<<endl;
            }
        }
    }
};

言歸正傳：

解：

法一： 暴力搜索

1.關(guān)鍵：

（1）子函數(shù) is_right(nums , start,end) : 傳遞3個參數(shù)，一個數(shù)組，一個起點下標，一個終點下標，然后判斷 從 下標start 到 end是否構(gòu)成 連續(xù)的 等差數(shù)組

(2) 主函數(shù) ：雙層循環(huán)

2.代碼（通過12個測試用例后 超時)

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        //法一：3重循環(huán)，暴力破解:
        int n = nums.size();
        int ans = 0 ;
        for(int i=0;i< n-2;i++)
        {
            for(int j=i+1;j< n;j++)
            {
                is_right(nums,i,j)
                {
                    ans++;
                }
            }
        }
        return ans;
    }
    bool is_right(vector<int> nums,int start,int end)
    {
        //從下標start 到 下標end，是否為一個等差序列
        if(end - start<2) return false;
        for(int i=start;i<=end-2;i++)
        {
            if(nums[i+1]*2 != nums[i] + nums[i+2])
            {
                return false;
            }
        }
        return true;
    }
};

法二： 滑動窗口的思想

1.關(guān)鍵：

（1）首先，下標i從0 到n-3作為外層 循環(huán)

(2)然后，計算2個元素 開頭的差值diff = nums[i+1] - nums[i]

（3）最后，內(nèi)層循環(huán)中，j從i+1 到n-2,如果nums[j+1] - nums[j] != diff 可以直接break掉這個內(nèi)層循環(huán)了，否則ans++

2.代碼:

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        //滑動窗口的思想:只要后面遇到一個地方的 nums[j+1] - nums[j] != diff
        //直接break這個 內(nèi)層循環(huán)， 否則ans++
        int ans =0 ;
        int n = nums.size();
        for(int i=0;i<=n-3;i++)
        {
            int diff = nums[i+1] - nums[i];
            for(int j=i+1;j<=n-2;j++)
            {
                if(nums[j+1] - nums[j] !=diff)
                {
                    break;
                }
                else
                {
                    ans++;
                }
            }
        }
        return ans;
    }
};

法三：動態(tài)規(guī)劃--遞推關(guān)系:

1.關(guān)鍵：

（1）dp[i]--含義：以nums數(shù)組中第i個元素 作為結(jié)束點的 最長的 連續(xù)等差序列

(2)遞推關(guān)系：

重點：分析nums[i] 和 nums[i-1]? ,? nums[i-2] 的關(guān)系，是否 可以“續(xù)上！”

2.代碼：

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        //動態(tài)規(guī)劃
        //dp[i]代表以nums[i]中第i個元素結(jié)束的連續(xù)等差數(shù)組的個數(shù)
        int n = nums.size();
        vector<int> dp(n,0);
        int sum = 0;
        for(int i =2;i<=n-1;i++)
        {
            if(nums[i] + nums[i-2] == nums[i-1]*2)
            {
                dp[i] = dp[i-1] + 1;
            }
            else
            {
                dp[i] = 0;
            }
            sum+=dp[i];
        }
        return sum;
    }
};

好了，動態(tài)規(guī)劃（一）的part1先到這里了，接下來就是part2部分了文章來源地址http://www.zghlxwxcb.cn/news/detail-418132.html

到了這里，關(guān)于動態(tài)規(guī)劃（一） part1的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！