動態規劃：示例、常見問題和解決方案

動態規劃問題會讓你在面試或考試中措手不及。在這裡檢視最常見的問題和解決方案。...

毫無疑問，動態規劃問題在編碼面試中可能會非常可怕。即使你知道一個問題需要用動態規劃方法來解決，在有限的時間內想出一個可行的解決方案也是一個挑戰。

精通動態規劃問題的最好方法是儘可能多地研究它們。雖然你不一定要記住每個問題的解決方案，但有一個如何著手實施的想法是很好的。

什麼是動態規劃(dynamic programming)？

簡單地說，動態規劃是遞迴演算法的一種最佳化方法，大多數遞迴演算法用於解決計算或數學問題。

你也可以稱之為一種演算法技術，透過將最佳化問題分解成更簡單的子問題來解決。動態規劃的一個關鍵原則是，問題的最優解取決於子問題的解。

每當我們看到一個遞迴解決方案對相同的輸入重複呼叫時，我們就可以使用動態規劃來最佳化它。其思想是簡單地儲存子問題的結果，這樣我們就不必在以後需要時重新計算它們。

動態程式設計的解決方案具有多項式複雜性，這確保了比遞迴或回溯等其他技術更快的執行時間。在大多數情況下，動態規劃減少了時間複雜性，也被稱為大O，從指數到多項式。

現在您已經對什麼是動態規劃有了一個很好的瞭解，是時候檢查一些常見的問題及其解決方案了。

動態規劃問題

1揹包問題

問題陳述

給定一組專案，每個專案都有一個權重和一個值，確定要包含在集合中的每個專案的數量，以便總權重不超過給定的限制，並且總值儘可能大。

我們為您提供了兩個整數陣列值[0..n-1]和權重[0..n-1]，它們分別表示與n個項相關聯的值和權重。同時給出了一個表示揹包容量的整數W。

這裡我們要解決0/1揹包問題，這意味著我們可以選擇新增或排除一個專案。

演算法

建立一個包含n+1行和w+1列的二維陣列。行號n表示從1到i的一組專案，列號w表示行李的最大承載能力。
[i][j]處的數值表示一個可攜帶最大重量j的袋子中直到i為止的物品的總價值。
在陣列中的每個座標[i][j]處，選取不帶i項的最大值，或帶i項的最大值，以較大者為準。
包括第一項所能獲得的最大值是第一項本身和揹包剩餘容量所能獲得的最大值之和。
執行此步驟，直到找到第w行的最大值。

程式碼

def FindMax(W, n, values, weights): MaxVals = [[0 for x in range(W + 1)] for x in range(n + 1)] for i in range(n + 1): for w in range(W + 1): if i == 0 or w == 0: MaxVals[i][w] = 0 elif weights[i-1] <= w: MaxVals[i][w] = max(values[i-1] + MaxVals[i-1][w-weights[i-1]], MaxVals[i-1][w]) else: MaxVals[i][w] = MaxVals[i-1][w] return MaxVals[n][W]

2硬幣兌換問題

問題陳述

假設給你一個數字陣列，代表每枚硬幣的價值。給定一個特定的數量，找出**這個數量所需的最小硬幣數量。

演算法

初始化大小為n+1的陣列，其中n是數量。將陣列中每個索引i的值初始化為等於amount。這表示組成該金額所需的最大硬幣數量（使用面額為1的硬幣）。
因為0沒有命名，所以初始化陣列[0]=0的基本情況。
對於每個其他索引i，我們將其中的值（最初設定為n+1）與值陣列[i-k]+1進行比較，其中k小於i。這基本上檢查整個陣列直到i-1，以找到我們可以使用的最小可能硬幣數。
如果任何陣列[i-k]+1處的值小於陣列[i]處的現有值，則將陣列[i]處的值替換為陣列[i-k]+1處的值。

程式碼

def coin_change(d, amount, k): numbers = [0]*(amount+1) for j in range(1, amount+1): minimum = amount for i in range(1, k+1): if(j >= d[i]): minimum = min(minimum, 1 + numbers[j-d[i]]) numbers[j] = minimum return numbers[amount]

三。斐波那契

問題陳述

斐波那契級數是一個整數序列，其中級數中的下一個整數是前兩個整數的和。

它由以下遞迴關係定義：F（0）=0，F（n）=F（n-1）+F（n-2），其中F（n）是第n項。在這個問題中，我們必鬚生成斐波那契數列中的所有數字，直到給定的第n項。

演算法

首先，使用遞迴方法實現給定的遞迴關係。
遞迴地解決這個問題需要將F（n）分解為F（n-1）+F（n-2），然後用F（n-1）和F（n+2）作為引數呼叫函式。我們這樣做，直到達到n=0或n=1的基本情況。
現在，我們使用一種叫做記憶的技術。將所有函式呼叫的結果儲存在一個數組中。這將確保每n，F（n）只需計算一次。
對於任何後續的計算，它的值可以簡單地從陣列中以恆定的時間獲取。

程式碼

def fibonacci(n): fibNums = [0, 1] for i in range(2, n+1): fibNums.append(fibNums[i-1] + fibNums[i-2]) return fibNums[n]

4子序列

問題陳述

求給定陣列中最長遞增子序列的長度。最長遞增子序列是一個遞增順序的數字陣列中的子序列。子序列中的數字必須是唯一的並按升序排列。

此外，序列的專案不需要是連續的。

演算法

從遞迴方法開始，計算從索引0到索引i的每個可能子陣列的最長遞增子序列的值，其中i小於或等於陣列的大小。
要將此方法轉換為動態方法，請建立一個數組來儲存每個子序列的值。將此陣列的所有值初始化為0。
該陣列的每個索引i對應於大小為i的子陣列的最長遞增子序列的長度。
現在，對於findLIS的每個遞迴呼叫（arr，n），檢查陣列的第n個索引。如果該值為0，則使用第一步中的方法計算該值，並將其儲存在第n個索引中。
最後，從陣列返回最大值。這是給定大小n的最長遞增子序列的長度。

程式碼

def findLIS(myArray): n = len(myArray) lis = [0]*n for i in range (1 , n): for j in range(0 , i): if myArray[i] > myArray[j] and lis[i]< lis[j] + 1 : lis[i] = lis[j]+1 maxVal= 0 for i in range(n): maxVal = max(maxVal , lis[i]) return maxVal