尋找鄭州網(wǎng)站優(yōu)化公司網(wǎng)絡(luò)推廣網(wǎng)站程序
?673. 最長遞增子序列的個數(shù)
673.?最長遞增子序列的個數(shù)
題目解析：
給定一個未排序的整數(shù)數(shù)組?nums?，?返回最長遞增子序列的個數(shù)?。
注意?這個數(shù)列必須是?嚴(yán)格?遞增的。
解題思路：
算法思路：
1. 狀態(tài)表?：
先嘗試定義?個狀態(tài)：以 i 為結(jié)尾的最?遞增?序列的「個數(shù)」。那么問題就來了，我都不知道
以 i 為結(jié)尾的最?遞增?序列的「?度」是多少，我怎么知道最?遞增?序列的個數(shù)呢？
因此，我們解決這個問題需要兩個狀態(tài)，?個是「?度」，?個是「個數(shù)」：
len[i] 表?：以 i 為結(jié)尾的最?遞增?序列的?度；
count[i] 表?：以 i 為結(jié)尾的最?遞增?序列的個數(shù)。
2. 狀態(tài)轉(zhuǎn)移?程：
求個數(shù)之前，我們得先知道?度，因此先看 len[i] ：
i. 在求 i 結(jié)尾的最?遞增序列的?度時，我們已經(jīng)知道 [0, i - 1] 區(qū)間上的 len[j]
信息，? j 表? [0, i - 1] 區(qū)間上的下標(biāo)；
ii. 我們需要的是遞增序列，因此 [0, i - 1] 區(qū)間上的 nums[j] 只要能和 nums[i]
構(gòu)成上升序列，那么就可以更新 dp[i] 的值，此時最??度為 dp[j] + 1 ；
iii. 我們要的是 [0, i - 1] 區(qū)間上所有情況下的最?值。
綜上所述，對于 len[i] ，我們可以得到狀態(tài)轉(zhuǎn)移?程為：
len[i] = max(len[j] + 1, len[i]) ，其中 0 <= j < i ，并且 nums[j] <
nums[i] 。
在知道每?個位置結(jié)尾的最?遞增?序列的?度時，我們來看看能否得到 count[i] ：
i. 我們此時已經(jīng)知道 len[i] 的信息，還知道 [0, i - 1] 區(qū)間上的 count[j] 信
息，? j 表? [0, i - 1] 區(qū)間上的下標(biāo)；
ii. 我們可以再遍歷?遍 [0, i - 1] 區(qū)間上的所有元素，只要能夠構(gòu)成上升序列，并且上
升序列的?度等于 dp[i] ，那么我們就把 count[i] 加上 count[j] 的值。這樣循
環(huán)?遍之后， count[i] 存的就是我們想要的值。
綜上所述，對于 count[i] ，我們可以得到狀態(tài)轉(zhuǎn)移?程為：
count[i] += count[j] ，其中 0 <= j < i ，并且 nums[j] < nums[i] &&
dp[j] + 1 == dp[i] 。
3. 初始化：
? 對于 len[i] ，所有元素??就能構(gòu)成?個上升序列，直接全部初始化為 1 ；
? 對于 count[i] ，如果全部初始化為 1 ，在累加的時候可能會把「不是最??度的情況」累
加進(jìn)去，因此，我們可以先初始化為 0 ，然后在累加的時候判斷?下即可。具體操作情況看代
碼~
4. 填表順序：
毫?疑問是「從左往右」。
5. 返回值：
? manLen 表?最終的最?遞增?序列的?度。
根據(jù)題?要求，我們應(yīng)該返回所有?度等于 maxLen 的?序列的個數(shù)。
?解題代碼：
class Solution {
public:int findNumberOfLIS(vector<int>& nums) {int n=nums.size();vector<int>dp(n,1);vector<int>f(n,1);int retlength=1;int retcount=1;for(int i=1;i<n;i++){//int length=f[0];//0到i-1區(qū)間內(nèi)的最大長度for(int j=0;j<i;j++){if(nums[j]<nums[i]){ if(f[j]+1==f[i])dp[i]+=dp[j];else if(f[j]+1>f[i]){dp[i]=dp[j];f[i]=f[j]+1;}} }if(retlength==f[i])retcount+=dp[i];else if(retlength<f[i]){retcount=dp[i];retlength=f[i];}}return retcount; }
};646. 最長數(shù)對鏈
??????646.?最長數(shù)對鏈
題目描述：
給你一個由?n?個數(shù)對組成的數(shù)對數(shù)組?pairs?，其中?pairs[i] = [lefti, righti]?且?lefti?< righti?。
現(xiàn)在，我們定義一種?跟隨?關(guān)系，當(dāng)且僅當(dāng)?b < c?時，數(shù)對?p2 = [c, d]?才可以跟在?p1 = [a, b]?后面。我們用這種形式來構(gòu)造?數(shù)對鏈?。
找出并返回能夠形成的?最長數(shù)對鏈的長度?。
你不需要用到所有的數(shù)對，你可以以任何順序選擇其中的一些數(shù)對來構(gòu)造。
解題思路：
算法思路：
這道題?讓我們在數(shù)對數(shù)組中挑選出來?些數(shù)對，組成?個呈現(xiàn)上升形態(tài)的最?的數(shù)對鏈。像不像
我們整數(shù)數(shù)組中挑選?些數(shù)，讓這些數(shù)組成?個最?的上升序列？因此，我們可以把問題轉(zhuǎn)化成我
們學(xué)過的?個模型： 300. 最?遞增?序列 。因此我們解決問題的?向，應(yīng)該在「最?遞增?序
列」這個模型上。
不過，與整形數(shù)組有所區(qū)別。在?動態(tài)規(guī)劃結(jié)局問題之前，應(yīng)該先把數(shù)組排個序。因為我們在計
算 dp[i] 的時候，要知道所有左區(qū)間? pairs[i] 的左區(qū)間?的鏈對。排完序之后，只?
「往前遍歷?遍」即可。
1. 狀態(tài)表?：
dp[i] 表?以 i 位置的數(shù)對為結(jié)尾時，最?數(shù)對鏈的?度。
2. 狀態(tài)轉(zhuǎn)移?程：
對于 dp[i] ，遍歷所有 [0, i - 1] 區(qū)間內(nèi)數(shù)對? j 表?下標(biāo)，找出所有滿? pairs[j]
[1] < pairs[i][0] 的 j 。找出??最?的 dp[j] ，然后加上 1 ，就是以 i 位置為結(jié)
尾的最?數(shù)對鏈。
3. 初始化：
剛開始的時候，全部初始化為 1 。
4. 填表順序：
根據(jù)「狀態(tài)轉(zhuǎn)移?程」，填表順序應(yīng)該是「從左往右」。
5. 返回值：
根據(jù)「狀態(tài)表?」，返回整個 dp 表中的最?值。
解題代碼：
class Solution {
public:int findLongestChain(vector<vector<int>>& pairs) {sort(pairs.begin(),pairs.end());int n=pairs.size();vector<int>dp(n,1);for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(pairs[j][1]<pairs[i][0])dp[i]=max(dp[i],dp[j]+1);}}int ret=1;for(int i=0;i<n;i++)ret=max(ret,dp[i]);return ret;}
};