一、題目描述
給你一個整數陣列 nums ，找到其中最長嚴格遞增子序列的長度，
子序列是由陣列派生而來的序列，洗掉（或不洗掉）陣列中的元素而不改變其余元素的順序，例如，[3,6,2,7] 是陣列 [0,3,1,6,2,2,7] 的子序列，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-increasing-subsequence
題目分析
如他的題目所描述，需要求出【最長遞增子序列】的【長度】，
幾個關鍵詞：最長、嚴格遞增、長度，
此處的嚴格遞增指：1,2,7,7的最長遞增子序列長度為3，因為7和7相等，沒有遞增，
舉幾個例子：如{0,3,1,6,2,2,7}它的遞增子序列有：{0,3,6,7} ,{0,1,6,7}, {0,1,2,7}以及一些更短的遞增子序列，而我們的目標就是求出這些子序列中長度的最大值，
二、用到的演算法思想
我解這道題用到的有：【動態規劃】(Dynamic Programming 簡稱DP)，
解題方式并不唯一，不要局限于一種方法，
三、思路
動態規劃解題四部曲（非準確）：找出原問題--->將原問題分解為規模更小的子問題--->當規模小到一定程度時，答案出現或者很容易求出--->將小的問題合并成原來的問題，
同樣以陣列 {0,3,1,6,2,2,7}為例：
我們可以很容易的有一種思路，前6個數的最長遞增子序列，前5個數.........
驗證這種思路是否可行：
{0,3,1,6,2,2,7} 的最長子序列長度為4，此時7在最長子序列當中，
在去掉7以后陣列變為
{0,3,1,6,2,2} 最長子序列為3，說明7在最長子序列中，除去也不影響子問題的解，
再將最后的2一處陣列，變為：
{0,3,1,6,2} 最長子序列依舊為3，說明除去的2不在最長子序列中，除去依舊不影響子問題的解，
......省略.....
由此可見，無論被移除陣列的那一位是否在最長子序列中，都不影響子問題的解，因此，這個問題具有【最優子結構性質】，
所以，我們已經無限接近答案了：
建立一個dp陣列，長度為【陣列長度+1】，
初始化：dp[0] = 0; dp[i] = 1; (i = 1,2,3...n);
接著為表中填入資料，從陣列arr第1位開始：填入1；
第2位：arr[1]與arr[0]比較，看arr[1]是否>arr[0]（即是否遞增），如果遞增，則判斷dp[i+1]和dp[i] + 1兩者誰大，
第3位：同2，但是需要回圈，直到陣列下標為0的位置.......
{0,3,1,6,2,2,7} 填入的最終dp陣列應該為: {0, 1, 2, 2, 3, 3, 3, 4}，
需要注意的是：最大值不一定在dp數字最后一位，如：{0,3,1,6,2,2,7,0,0,0} 它最終的dp陣列為：{0, 1, 2, 2, 3, 3, 3, 4, 1,1, 1}， 所以需要回圈一次dp陣列找出最大值，
四、代碼實作（Java）
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length+1];
dp[0] = 0;
for(int i = 0; i < nums.length; i++){
dp[i+1] = 1;
for(int j = i; j >= 0; j--){
if(nums[i] > nums[j]){
dp[i+1] = getMax(dp[j+1]+1, dp[i+1]);
}
}
}
int max = 0;
for(int i = 0; i <= nums.length; i++){
if(dp[i] > max)
max = dp[i];
}
return max;
}
public int getMax(int m, int n){
return m > n ? m : n;
}
}
五、完成時間
2021-01-28 15:48:57
最近幾天在研究動態規劃，刷了七八道題，漸漸地有了一些感覺，但動態規劃也分好多種類，比如區間dp，背包dp，樹形dp等等，需要多加努力，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/253859.html
標籤：其他