?300. 最長遞增子序列
300.?最長遞增子序列
題目解析：
給你一個整數數組?nums?，找到其中最長嚴格遞增子序列的長度。
子序列?是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其余元素的順序。例如，[3,6,2,7]?是數組?[0,3,1,6,2,2,7]?的子序列。
解題思路：、
1. 狀態表?：
對于線性 dp ，我們可以?「經驗 + 題?要求」來定義狀態表?：
i. 以某個位置為結尾，巴拉巴拉；
ii. 以某個位置為起點，巴拉巴拉。
這?我們選擇?較常?的?式，以某個位置為結尾，結合題?要求，定義?個狀態表?：
dp[i] 表?：以 i 位置元素為結尾的「所有?序列」中，最?遞增?序列的?度。
2. 狀態轉移?程：
對于 dp[i] ，我們可以根據「?序列的構成?式」，進?分類討論：
i. ?序列?度為 1 ：只能??玩了，此時 dp[i] = 1 ；
ii. ?序列?度?于 1 ： nums[i] 可以跟在前?任何?個數后?形成?序列。
設前?的某?個數的下標為 j ，其中 0 <= j <= i - 1 。
只要 nums[j] < nums[i] ， i 位置元素跟在 j 元素后?就可以形成遞增序列，?度
為 dp[j] + 1 。
因此，我們僅需找到滿?要求的最?的 dp[j] + 1 即可。
綜上， dp[i] = max(dp[j] + 1, dp[i]) ，其中 0 <= j <= i - 1 && nums[j]
< nums[i] 。
3. 初始化：
所有的元素「單獨」都能構成?個遞增?序列，因此可以將 dp 表內所有元素初始化為 1 。
由于?到前?的狀態，因此我們循環的時候從第?個位置開始即可。
4. 填表順序：
顯?易?，填表順序「從左往右」。
5. 返回值：
由于不知道最?遞增?序列以誰結尾，因此返回 dp 表??的「最?值」。
?解題代碼：
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n=nums.size();vector<int>dp(n,1);for(int i=1;i<n;i++){for(int j =0;j<i;j++){if(nums[j]<nums[i])dp[i]=max(dp[i],dp[j]+1);}}int ret=0;for(int i=0;i<n;i++)ret=max(ret,dp[i]);return ret;}
};?376. 擺動序列
376.?擺動序列
題目描述：
如果連續數字之間的差嚴格地在正數和負數之間交替，則數字序列稱為?擺動序列 。第一個差（如果存在的話）可能是正數或負數。僅有一個元素或者含兩個不等元素的序列也視作擺動序列。
-
例如，?
[1, 7, 4, 9, 2, 5]?是一個?擺動序列?，因為差值?(6, -3, 5, -7, 3)?是正負交替出現的。 - 相反，
[1, 4, 7, 2, 5]?和?[1, 7, 4, 5, 5]?不是擺動序列，第一個序列是因為它的前兩個差值都是正數，第二個序列是因為它的最后一個差值為零。
子序列?可以通過從原始序列中刪除一些（也可以不刪除）元素來獲得，剩下的元素保持其原始順序。
給你一個整數數組?nums?，返回?nums?中作為?擺動序列?的?最長子序列的長度?。
?解題思路：
1. 狀態表?：
對于線性 dp ，我們可以?「經驗 + 題?要求」來定義狀態表?：
i. 以某個位置為結尾，巴拉巴拉；
ii. 以某個位置為起點，巴拉巴拉。
這?我們選擇?較常?的?式，以某個位置為結尾，結合題?要求，定義?個狀態表?：
dp[i] 表?「以 i 位置為結尾的最?擺動序列的?度」。
但是，問題來了，如果狀態表?這樣定義的話，以 i 位置為結尾的最?擺動序列的?度我們沒法
從之前的狀態推導出來。因為我們不知道前?個最?擺動序列的結尾處是遞增的，還是遞減的。因
此，我們需要狀態表?能表?多?點的信息：要能讓我們知道這?個最?擺動序列的結尾是遞增的
還是遞減的。
解決的?式很簡單：搞兩個 dp 表就好了。
f[i] 表?：以 i 位置元素為結尾的所有的?序列中，最后?個位置呈現「上升趨勢」的最?擺
動序列的?度；
g[i] 表?：以 i 位置元素為結尾的所有的?序列中，最后?個位置呈現「下降趨勢」的最?擺
動序列的?度。
2. 狀態轉移?程：
由于?序列的構成?較特殊， i 位置為結尾的?序列，前?個位置可以是 [0, i - 1] 的任意
位置，因此設 j 為 [0, i - 1] 區間內的某?個位置。
對于 f[i] ，我們可以根據「?序列的構成?式」，進?分類討論：
i. ?序列?度為 1 ：只能??玩了，此時 f[i] = 1 ；
ii. ?序列?度?于 1 ：因為結尾要呈現上升趨勢，因此需要 nums[j] < nums[i] 。在滿
?這個條件下， j 結尾需要呈現下降狀態，最?的擺動序列就是 g[j] + 1 。
因此我們要找出所有滿?條件下的最?的 g[j] + 1 。
綜上， f[i] = max(g[j] + 1, f[i]) ，注意使? g[j] 時需要判斷。
對于 g[i] ，我們可以根據「?序列的構成?式」，進?分類討論：
i. ?序列?度為 1 ：只能??玩了，此時 g[i] = 1 ；
ii. ?序列?度?于 1 ：因為結尾要呈現下降趨勢，因此需要 nums[j] > nums[i] 。在滿
?這個條件下， j 結尾需要呈現上升狀態，因此最?的擺動序列就是 f[j] + 1 。
因此我們要找出所有滿?條件下的最?的 f[j] + 1 。
綜上， g[i] = max(f[j] + 1, g[i]) ，注意使? f[j] 時需要判斷。
3. 初始化：
所有的元素「單獨」都能構成?個擺動序列，因此可以將 dp 表內所有元素初始化為 1 。
4. 填表順序：
毫?疑問是「從左往右」。
5. 返回值：
應該返回「兩個 dp 表??的最?值」，我們可以在填表的時候，順便更新?個「最?值」。
解題代碼：
class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int n=nums.size();if(n==1)return 1;if(n==2&&nums[0]!=nums[1])return 2;vector<int>f(n,1);vector<int>g(n,1);for(int i=1;i<n;i++){for(int j=0;j<i;j++){if(nums[i]>nums[j])f[i]=max(g[j]+1,f[i]);if(nums[i]<nums[j])g[i]=max(f[j]+1,g[i]);}}int ret=0;for(int i=0;i<n;i++)ret=max(ret,max(f[i],g[i]));return ret;}
};
)
)
 C++代碼)
