【問題描述】[中等]

給定一個無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度。示例:輸入: [10,9,2,5,3,7,101,18] 輸出: 4 解釋: 最長的上升子序列是 [2,3,7,101]，它的長度是 4。 說明:可能會有多種最長上升子序列的組合，你只需要輸出對應(yīng)的長度即可。 你算法的時間復(fù)雜度應(yīng)該為 O(n2) 。 進階: 你能將算法的時間復(fù)雜度降低到 O(n log n) 嗎?

【解答思路】

1. 動態(tài)規(guī)劃

時間復(fù)雜度：O(N^2) 空間復(fù)雜度：O(N)

import java.util.Arrays;public class Solution {public int lengthOfLIS(int[] nums) {int len = nums.length;if (len < 2) {return len;}int[] dp = new int[len];Arrays.fill(dp, 1);for (int i = 1; i < len; i++) {for (int j = 0; j < i; j++) {if (nums[j] < nums[i]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}}int res = 0;for (int i = 0; i < len; i++) {res = Math.max(res, dp[i]);}return res;} }

2. 動態(tài)規(guī)劃壓縮空間（貪心+二分）

時間復(fù)雜度：O(NlogN) 空間復(fù)雜度：O(N)

public class Solution {public int lengthOfLIS(int[] nums) {int len = nums.length;if (len <= 1) {return len;}// tail 數(shù)組的定義：長度為 i + 1 的上升子序列的末尾最小是幾int[] tail = new int[len];// 遍歷第 1 個數(shù)，直接放在有序數(shù)組 tail 的開頭tail[0] = nums[0];// end 表示有序數(shù)組 tail 的最后一個已經(jīng)賦值元素的索引int end = 0;for (int i = 1; i < len; i++) {// 【邏輯 1】比 tail 數(shù)組實際有效的末尾的那個元素還大if (nums[i] > tail[end]) {// 直接添加在那個元素的后面，所以 end 先加 1end++;tail[end] = nums[i];} else {// 使用二分查找法，在有序數(shù)組 tail 中// 找到第 1 個大于等于 nums[i] 的元素，嘗試讓那個元素更小int left = 0;int right = end;while (left < right) {// 選左中位數(shù)不是偶然，而是有原因的，原因請見 LeetCode 第 35 題題解// int mid = left + (right - left) / 2;int mid = left + ((right - left) >>> 1);if (tail[mid] < nums[i]) {// 中位數(shù)肯定不是要找的數(shù)，把它寫在分支的前面left = mid + 1;} else {right = mid;}}// 走到這里是因為 【邏輯 1】 的反面，因此一定能找到第 1 個大于等于 nums[i] 的元素// 因此，無需再單獨判斷tail[left] = nums[i];}// 調(diào)試方法// printArray(nums[i], tail);}// 此時 end 是有序數(shù)組 tail 最后一個元素的索引// 題目要求返回的是長度，因此 +1 后返回end++;return end;}// 調(diào)試方法，以觀察是否運行正確private void printArray(int num, int[] tail) {System.out.print("當(dāng)前數(shù)字：" + num);System.out.print("\t當(dāng)前 tail 數(shù)組：");int len = tail.length;for (int i = 0; i < len; i++) {if (tail[i] == 0) {break;}System.out.print(tail[i] + ", ");}System.out.println();}public static void main(String[] args) {int[] nums = new int[]{3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12};Solution solution = new Solution8();int lengthOfLIS = solution8.lengthOfLIS(nums);System.out.println("最長上升子序列的長度：" + lengthOfLIS);} }

【總結(jié)】

1.子序列和子串

2.動態(tài)規(guī)劃（高度概括）

第 1 步：設(shè)計狀態(tài)
第 2 步：狀態(tài)轉(zhuǎn)移方程
第 3 步：考慮初始化
第 4 步：考慮輸出
第 5 步：考慮是否可以狀態(tài)壓縮

3.動態(tài)規(guī)劃（詳細說明）

1、思考狀態(tài)（重點）

狀態(tài)的定義，先嘗試「題目問什么，就把什么設(shè)置為狀態(tài)」；
然后思考「狀態(tài)如何轉(zhuǎn)移」，如果「狀態(tài)轉(zhuǎn)移方程」不容易得到，嘗試修改定義，目的依然是為了方便得到「狀態(tài)轉(zhuǎn)移方程」。
「狀態(tài)轉(zhuǎn)移方程」是原始問題的不同規(guī)模的子問題的聯(lián)系。即大問題的最優(yōu)解如何由小問題的最優(yōu)解得到。

2、思考狀態(tài)轉(zhuǎn)移方程（核心、難點）

狀態(tài)轉(zhuǎn)移方程是非常重要的，是動態(tài)規(guī)劃的核心，也是難點；

常見的推導(dǎo)技巧是：分類討論。即：對狀態(tài)空間進行分類；

歸納「狀態(tài)轉(zhuǎn)移方程」是一個很靈活的事情，通常是具體問題具體分析；

除了掌握經(jīng)典的動態(tài)規(guī)劃問題以外，還需要多做題；

如果是針對面試，請自行把握難度。掌握常見問題的動態(tài)規(guī)劃解法，理解動態(tài)規(guī)劃解決問題，是從一個小規(guī)模問題出發(fā)，逐步得到大問題的解，并記錄中間過程；

「動態(tài)規(guī)劃」方法依然是「空間換時間」思想的體現(xiàn)，常見的解決問題的過程很像在「填表」。

3、思考初始化

初始化是非常重要的，一步錯，步步錯。初始化狀態(tài)一定要設(shè)置對，才可能得到正確的結(jié)果。

角度 1：直接從狀態(tài)的語義出發(fā)；

角度 2：如果狀態(tài)的語義不好思考，就考慮「狀態(tài)轉(zhuǎn)移方程」的邊界需要什么樣初始化的條件；

角度 3：從「狀態(tài)轉(zhuǎn)移方程」方程的下標(biāo)看是否需要多設(shè)置一行、一列表示「哨兵」（sentinel），這樣可以避免一些特殊情況的討論。

4、思考輸出

有些時候是最后一個狀態(tài)，有些時候可能會綜合之前所有計算過的狀態(tài)。

5、思考優(yōu)化空間（也可以叫做表格復(fù)用）

「優(yōu)化空間」會使得代碼難于理解，且是的「狀態(tài)」丟失原來的語義，初學(xué)的時候可以不一步到位。先把代碼寫正確是更重要；
「優(yōu)化空間」在有一種情況下是很有必要的，那就是狀態(tài)空間非常龐大的時候（處理海量數(shù)據(jù)），此時空間不夠用，就必須「優(yōu)化空間」；
非常經(jīng)典的「優(yōu)化空間」的典型問題是「0-1 背包」問題和「完全背包」問題。

4. 動態(tài)規(guī)劃思考

• 邊界問題考慮清楚（第二第三步）
• 動態(tài)就是做表格 想清楚方向
• 自底向上 子問題 學(xué)基礎(chǔ) 再解決問題 通識教育
• 自頂向下 一般解決問題思路
  

轉(zhuǎn)載鏈接：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/

總結(jié)

以上是生活随笔為你收集整理的[Leedcode][JAVA][第300题][最长上上子序列][动态规划][压缩空间]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。