摘要:數鍵盤雖然是一個很簡單的游戲,但是解答的過程中已經包含了最基礎的動態規劃解題思路定義狀態再重新定義問題找到最基礎的狀態找出狀態轉移方程編程求解最長上升子序列問給定一個無序的整數數組,找到其中最長上升子序列的長度。
算法能力就是程序員的內力,內力強者對編程利劍的把控能力就更強。
數鍵盤動態規劃就是,通過遞推的方式,由最基本的答案推導出更復雜答案的方法,直到找到最終問題的解。或者是,通過遞歸的方式,將復雜問題化解為更簡單問題的方法,直到化解為有明確答案的最基礎問題。
問:你現在用的鍵盤上有多少個鍵帽?
當我問你這個問題時,你一定想到了解決方案,一個個數肯定能得到答案。
我們可以把這個簡單的問題,用公式定義的更加清楚:設 F(n) 為鍵帽的總數,求 F(n) 的值。當你開始數第一個的鍵帽的時候,你得到了 F(1) = 1,這是一個最基本的答案。數數過程中,下一個答案等于上一個答案加 1。在狀態規劃中,我們通常把階段性的答案,稱作狀態。復雜狀態與簡單狀態之間存在的轉化關系,叫做狀態轉移方程,狀態轉移方程是動態規范的核心,這這道題目中就是:
F(i) = F(i - 1) + 1 ( 0當我們使用遞推的方式,來求解動態規劃時,我們會從 1 開始數起,一步步累加得到最終的狀態:
F(1) = 1 F(2) = F(1) + 1 ... F(N) = f(N-1) + 1當我們使用遞歸的方式,來求解動態規劃時,我們會從把所有的鍵帽數量,記作狀態 F(N),當我們數了一個鍵帽后,那么 剩下的狀態就記作 F(N-1),因此:
F(N) = F(N-1) + 1 F(N-1) = F(N-2) + 1 ... F(1) = 1無論是遞推還是遞歸,都是得到的答案無疑都是一樣的,只不過思維的方式有些不一樣。遞推是正向思維,先有基礎答案后由復雜答案,最后得出最終問題的答案。遞歸是逆向思維,先有復雜的問題,然后把它化解為更簡單的問題,直到分解為能一眼看出答案的基本問題。
數鍵盤雖然是一個很簡單的游戲,但是解答的過程中已經包含了最基礎的動態規劃解題思路:
定義狀態
再重新定義問題
找到最基礎的狀態
找出狀態轉移方程
編程求解
最長上升子序列問:給定一個無序的整數數組,找到其中最長上升子序列的長度。
示例:
輸入: [10,9,2,5,3,7,101,18] 輸出: 4 解釋: 最長的上升子序列是 [2,3,7,101],它的長度是 4。說明:
可能會有多種最長上升子序列的組合,你只需要輸出對應的長度即可。
你算法的時間復雜度應該為 O(n2) 。
這道題目的問題是,求最長上升子序列的長度。直接拿到這個問題,肯定一臉懵逼,最長上升子序列的長度是什么?斷詞斷句一個個解釋,序列、子序列、上升序列、最長上升子序列的長度。
序列:這里指的是,一個無序的整數數組。
子序列:將原序列中的部分值,重新組合成一個新的序列,這個新的序列就是子序列。一個序列可以有多個子序列。如,原序列 [1, 5, 2, 3],那么 [1, 5] 和 [1, 2, 3] 都是原序列的子序列。
上升序列:從前往后看,序列中的前面的數字比后面的數字更小,序列呈遞增規律,就是上升序列。[1, 2, 3] 就是上升序列,[1,2,0] 就不是上升序列。
最長上升子序列的長度:一個序列可能會有多個上升子序列,其中長度最長的叫做最長上升子序列,其長度叫做最長上升子序列的長度。
動態規劃方法一第一步:定義狀態。定義狀態為,以當前序列第 i 個數字結尾的最長上升子序列的長度,記作 L(i),0≤i≤N-1,N為序列長度。示例:序列[1,2,3],狀態 L[1] = 2 ,表示第 1 個以 2 結尾的最長上升子序列的長度為 2。
第二步:重新定位問題。序列中的最長上升子序列,不一定是以最后一個數字結尾,而是所有狀態中的最大值,即 Math.max(L[0],L[1],…,L(N-1))。示例:[1,2,0] 的最長上升子序列是 [1,2] ,是以第1個數字結尾的。
第三步:找到最基礎的狀態。當序列為空時,結尾的最長上升子序列的長度為0。但是我們發現,最初我們定義的狀態,并不能表示該最基礎的狀態,因此需要對狀態的定義稍作修正。
狀態:以當前序列第 index 個數字結尾的最長上升子序列的長度,index 是序列的下標,記 i = index + 1 ,狀態為 L(i),0≤i≤N,N為序列長度。此時 L[0] 表示空序列的最長上升子序列的長度 L[0] = 0,L[1] 表示以序列中第 0 位數字結尾的最長上升子序列的長度,L[1] = 1。
第四步:找到狀態轉移方程。若 L[i] 大于 1,則 L[i] 表示的子序列,去掉最后一位數,依舊是一個子序列,記該子序列為 L[j] 。其關系為 L[i] = L[j] + 1 。其中 L[j] 的最后一位 nums[j -1] < nums[i - 1],且 L[j] = Math.max( L[1],…,L[i-1]) ,0
例如:序列A [1, 2, 6, 3, 4]
1. L[0] = 0 2. L[1] = 1 3. L[2] = Math.max( L[1]) + 1 = L[1] + 1 = 2, 其中 nums[1-1] < nums[2-1] 4. L[3] = Math.max(L[1], L[2]) + 1 = L[2] + 1 = 2, 其中 nums[2-1] < nums[3-1] 5. L[4] = Math.max(L[1], L[2],L[3]) + 1 = L[2] + 1 = 2, 其中 nums[2-1] < nums[4-1] 6. L[5] = Math.max(L[1], L[2],L[3],L[4]) + 1 = L[4] + 1 = 2, 其中 nums[4-1] < nums[5-1]變成為:
function lengthOfLIS(nums) { const dp = [0] for (let i = 1; i <= nums.length; i++) { let max = 0 for (let j = 1; j < i; j++) { if (nums[j - 1] < nums[i - 1]) { max = Math.max(max, dp[j]) } } dp[i] = max + 1 } return Math.max(...dp) };動態規劃方法二第一步:定義狀態。在序列前 index 項中,所有可能成為最長上升子序列的子序列。S[i]
示例:A [10, 1, 12, 2, 3] S[0] = [[10]] S[1] = [[10], [1]] S[2] = [[10, 12], [1, 12]] S[3] = [[10, 12], [1, 12], [1, 2]] S[4] = [[10, 12], [1, 12], [1, 2, 3]]當 S[1] = [[10], [1]] 時,A[2] 存在三種情況,①當 10 < A[2] 時, [10, A[2]] 和 [1, A[2]] 表示的長度等價;②當 1 < A[2] ≤ 10 時, [1, A[2]] 比 [10] 長;③當 A[2] ≤ 1 時,S[3] = [[10], [1], A[3]]。
因為題目只需要返回最終長度,所以 [10] 或 [1] 兩種情況實際,可以簡寫為 [1] 這一種情況。A[3] 存在 3中情況,分別為①當 10 < A[2] 時, [1, A[2]] ;②當 1 < A[2] ≤ 10 時, [1, A[2]];③當 A[2] ≤ 1 時,S[3] = [A[3]]。因此可證明,只保留 [1] 一種情況,實際上已經代表了 [10] 或 [1] 兩種情況。
對狀態進行重新定義:在序列前 i 項中,長度為 k 的上升子序列中,最后一位的最小值。S[i]
示例:A [10, 1, 12, 2, 3] S[0] = [10] S[1] = [1] S[2] = [1,12] S[3] = [1,2] S[4] = [1,2,3]第二步:重新定位問題。 求 S[N-1] 的長度,其中 N 為序列的長度。
第三步:找到最基礎的狀態。當序列為空時,結尾的最長上升子序列的長度為0,因此對問題和狀態進行重新修正。
狀態:在序列前 i + 1 項中,長度為 k 的上升子序列中,最后一位的最小值。S[i]
問題:求 S[N] 的長度,其中 N 為序列的長度。
第四步:找到狀態轉移方程。如果 A[i-1] 比 S[i] 最后一位還要大,記作 S[i][len -1] < A[i-1] ,即可以組成一個更長子序列,s[i] = [...s[i -1],A[i-1]]。如果 A[i-1] 比 S[i] 中某一位 S[i][j]要小,但是比該位的前一位 S[i][j-1]要大,更具第一步中的推論,可以用 A[i-1] 替換掉 S[i][j] ,S[i] = […,S[i][j-1],A[i-1] ,…]
示例:A [10, 1, 12, 2, 3] S[0] = [] // 初始化 S[1] = [10] // 在最后添加 A[1-1]=10 S[2] = [1] // A[2-1] < S[2][0],因此替換掉 S[2][0] S[3] = [1,12] // 在最后添加 A[3-1]= 12 S[4] = [1,2] // S[2][0] < A[2-1] < S[2][1],因此替換掉 S[2][1] S[5] = [1,2,3] // 在最后添加 A[5-1]= 3實現:
function lengthOfLIS(nums) { const sequence = [] // 復雜度 n for (let i = 1; i <= nums.length; i++) { let len = sequence.length // 增加 if (sequence[len - 1] < nums[i-1]) { sequence[len] = nums[i-1] // 替換 } else { // sequence 具有單調性,可以使用 logn 復雜度的二分查找,查找到 S[i][j-1]
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/103470.html
摘要:題目給定兩個字符串求出它們的最長公共字串說明比如在單詞和它們的最長公共子序列是。最長公共子串和最長公共子序列的區別。 題目 給定兩個字符串,求出它們的最長公共字串 var str1=abcdefg; var str2=xyzabcd; 說明:比如在單詞abcdefg和abcdefg它們的最長公共子序列是abcd。尋找最長子序列常用于遺傳學中,用于使用核苷酸堿基的首字母對DNA的描述(這...
摘要:代碼實現在控制臺打印總結本篇文章帶大家搭好環境,并體驗了控制臺打印。輸出結果總結熟練掌握取余和整除運算,大有作用。終止本次循環,繼續執行下一次循環。 ?本文收錄...
摘要:動態規劃有時被稱為遞歸的相反的技術。動態規劃方案通常使用一個數組來建立一張表,用于存放被分解成眾多子問題的解。今天我們先從我們最熟的斐波那契數列數列開始。斐波那契數列在很多地方都會用上,我是從一個臺階問題發現的,同時知道了動態規劃的解法。 前段時間一直寫了幾個算法題目,發現有個很牛逼的算法,動態規劃,雖然有的解題思路和動態規劃很像,但是當時不知道其中的原理和一些通用性,接下來的幾天,通...
閱讀 2224·2021-11-22 09:34
閱讀 1334·2021-10-11 10:59
閱讀 4427·2021-09-22 15:56
閱讀 3270·2021-09-22 15:08
閱讀 3401·2019-08-30 14:01
閱讀 773·2019-08-30 11:16
閱讀 1129·2019-08-26 13:51
閱讀 2906·2019-08-26 13:43