建立二维数组_二维数组的 DP
尋找不同路徑和
一個機器人位于一個 m x n 網格的左上角 (起始點在下圖中標記為“Start” )。
機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角(在下圖中標記為“Finish”)。
問總共有多少條不同的路徑?
例如,上圖是一個7 x 3 的網格。有多少可能的路徑?
動態規劃5大步驟:
1.定義狀態:
即定義數據元素的含義,這里定義dp[i][j]為當前位置的路徑數,i表示i列,j表示j行。注意,這個網格相當于一個二維數組,數組是從下標為 0 開始算起的,所以 右下角的位置是 (m-1, n - 1),所以 dp[m-1] [n-1] 就是我們要找的答案。
2.建立狀態轉移方程:
因為從題目要求中可以看出,機器人只能向右或向下移動。
所以到達dp[i][j]就可能是經過dp[i-1][j]到達,也可能是經過dp[i][j-1]到達。
所以狀態轉移方程為:dp[i][j]=dp[i-1][j]+dp[i][j-1]
3.設定初始值:
通過狀態轉移方程可以看出,i和j下表要從1開始,否則會導致數組溢出異常。因為這個時候把 i - 1 或者 j - 1,就變成負數了,數組就會出問題了。同時每一個位置點代表到達當前位置的路徑條數,所以要設置最初的路徑條數即第一行,第一列值為1。
dp[i][0]=1(相當于最上面一行,機器人只能一直往右走),
dp[0][j]=1,(相當于最左面一列,機器人只能一直往下走)
4.狀態壓縮:
上面時間復雜度:
,空間復雜度: ,優化目標即優化數組空間,每次狀態的更新只依賴于前一次的狀態,優化一般作用于多維數組,觀察是否可以將多維數組以一維數組來動態表示,即用一維數組來保存上次的狀態,動態計算并替換當前位置下的路徑數最新值。這道題的優化方法是存在的。
當我們要填充第三行的值的時候,我們需要用到第一行的值嗎?根據公式 dp[i][j] = dp[i-1][j] + dp[i][j-1],我們可以知道,當我們要計算第 j 行的值時,只用到第 j - 1 行。我們只需要用一個一維的 dp[] 來保存一行的歷史記錄就可以了。
1、剛開始初始化第一行,此時 dp[0..m-1] 的值就是第一行的值。
2、接著我們來一邊填充第二行的值一邊更新 dp[i] 的值,一邊把第一行的值拋棄掉。
(1)、顯然,矩陣(1, 0) 的值相當于以往的初始化值,為 1。然后這個時候矩陣 (0,0)的值不在需要保存了,因為再也用不到了。這個時候,我們也要跟著更新 dp[0] 的值了,剛開始 dp[0] = (0, 0),現在更新為 dp[0] = (1, 0)。
(2)、接著繼續更新 (1, 1) 的值,根據之前的公式 dp[i][j] = dp[i-1][j] + dp[i][j-1]。即 (1,1)=(0,1)+(1,0)=2。
以往的二維的時候, dp[i][j] = dp[i-1] [j]+ dp[i][j-1]。現在轉化成一維,不就是 dp[i] = dp[i] + dp[i-1]
即 dp[1] = dp[1] + dp[0],而且還動態幫我們更新了 dp[1] 的值。因為剛開始 dp[i] 的保存第一行的值的,現在更新為保存第二行的值。
狀態轉移方程:dp[i] = dp[i-1] + dp[i].
初始值: f = [1]*m,取橫軸
5.選出結果:
根據狀態轉移方程,求路徑的總數,因此 dp[m-1] [n-1]表示的是到達最后位置的路徑總條數。
def uniquePaths( m, n):f = [[0]*n for zong in range(m)]for i in range(m):f[i][0] = 1for j in range(n):f[0][j] = 1for i in range(1,m):for j in range(1,n):f[i][j] = f[i-1][j]+f[i][j-1]return f[m-1][n-1]優化:
def uniquePaths( m, n):f = [1]*mfor j in range(1,n):for i in range(1,m):f[i] = f[i-1]+f[i]return f[m-1]最小路徑和
給定一個包含非負整數的 m x n 網格,請找出一條從左上角到右下角的路徑,使得路徑上的數字總和為最小。
說明:每次只能向下或者向右移動一步。
示例:
輸入:
[[1,3,1],[1,5,1],[4,2,1]
]
輸出: 7
解釋: 因為路徑 1→3→1→1→1 的總和最小。動態規劃5大步驟:
1.定義狀態:
即定義數據元素的含義,這里定義dp[i][j]為當前位置的最小路徑和,i表示i列,j表示j行。注意,這個網格相當于一個二維數組,數組是從下標為 0 開始算起的,所以 右下角的位置是 (m-1, n - 1),所以 dp[m-1] [n-1] 就是我們要找的答案。
2.建立狀態轉移方程:
因為從題目要求中可以看出,只能向右或向下移動。
所以到達dp[i][j]就可能是經過dp[i-1][j]到達,也可能是經過dp[i][j-1]到達。
不過這次不是計算所有可能路徑,而是計算哪一個路徑和是最小的,那么我們要從這兩種方式中,選擇一種,使得dp[i] [j] 的值是最小的,顯然有
所以狀態轉移方程為:
;arr[i][j] 表示當前位置路徑值
3.設定初始值:
通過狀態轉移方程可以看出,i和j下標要從1開始,否則會導致數組溢出異常。因為這個時候把 i - 1 或者 j - 1,就變成負數了,數組就會出問題了。同時每一個位置點代表到達當前位置的路徑值,所以要設置最初的最小路徑和即
當只有左邊是矩陣邊界時: 只能從上面來,即當
時, dp[i][j] = dp[i][j - 1] + arr[i] [j] ;當只有上邊是矩陣邊界時: 只能從左面來,即當
時, dp[i][j] = dp[i - 1][j] + arr[i][j] ;當左邊和上邊都是矩陣邊界時: 即當i = 0, j = 0時,其實就是起點, dp[i][j] = arr[i][j]
4.狀態壓縮:
其實我們完全不需要建立 dp 矩陣浪費額外空間,直接遍歷 arr[i][j] 修改即可。這是因為:arr[i][j] = min(arr[i - 1][j], arr[i][j - 1]) + arr[i][j] ;原 arr矩陣元素中被覆蓋為 dp 元素后(都處于當前遍歷點的左上方),不會再被使用到。
復雜度分析:
時間復雜度
: 遍歷整個 arr 矩陣元素。空間復雜度 O(1): 直接修改原矩陣,不使用額外空間
5.選出結果:
根據狀態轉移方程,求路徑的總數,因此 arr[m-1] [n-1]表示的是到達最后位置的最小路徑和
def MinPathSum(arr:[[int]]):for i in range(len(arr)):for j in range(len(arr[0])):if i == j == 0:continueelif i==0: arr[i][j] = arr[i][j-1] + arr[i][j]elif j==0: arr[i][j] = arr[i-1][j] + arr[i][j]else:arr[i][j] = min(arr[i-1][j],arr[i][j-1])+arr[i][j]return arr[i-1][j-1]編輯距離
給你兩個單詞 word1 和 word2,請你計算出將 word1 轉換成 word2 所使用的最少操作數 。
你可以對一個單詞進行如下三種操作:
插入一個字符
刪除一個字符
替換一個字符
示例 1:
輸入:word1 = "horse", word2 = "ros"
輸出:3
解釋:
horse -> rorse (將 'h' 替換為 'r')
rorse -> rose (刪除 'r')
rose -> ros (刪除 'e')示例 2:
輸入:word1 = "intention", word2 = "execution"
輸出:5
解釋:
intention -> inention (刪除 't')
inention -> enention (將 'i' 替換為 'e')
enention -> exention (將 'n' 替換為 'x')
exention -> exection (將 'n' 替換為 'c')
exection -> execution (插入 'u')解答
還是老樣子,按照上面步驟來,并且我這里可以告訴你,90% 的字符串問題都可以用動態規劃解決,并且90%是采用二維數組。
步驟一、定義狀態:
由于我們的目的求將 word1 轉換成 word2 所使用的最少操作數 。那我們就定義 dist[i] [j]的含義為:當字符串 word1 的長度為 i,字符串 word2 的長度為 j 時,將 word1 轉化為 word2 所使用的最少操作次數為 dp[i] [j]。
步驟二:建立狀態轉移方程:
接下來我們就要找 dist[i] [j] 元素之間的關系了,比起其他題,這道題相對比較難找一點,但是,不管多難找,大部分情況下,dist[i] [j] 和 dist[i-1] [j]、disti] [j-1]、dist[i-1] [j-1] 肯定存在某種關系。因為我們的目標就是,從規模小的,通過一些操作,推導出規模大的。對于這道題,我們可以對 word1 進行三種操作
插入一個字符 刪除一個字符 替換一個字符
由于我們是要讓操作的次數最小,所以我們要尋找最佳操作。那么有如下關系式:
1、若word1[i] == word2[j],新字符相等,無需增加編輯距離即可直接轉換,即dist[i][j] = dist[i-1][j-1] 
2、如果我們 word1[i] 與 word2 [j] 不相等,這個時候我們就必須進行調整,而調整的操作有 3 種,我們要選擇一種。三種操作對應的關系試如下(注意字符串與字符的區別):
(1)刪除,最后操作是對word1刪除1個字符,,意味著刪掉word1[i]后兩單詞匹配,
也就是在word1[:i-1]和word2[:j]完成轉換的基礎上增加一次刪除操作實現,即dist[i][j] = dist[i-1][j] + 1
(2)插入,最后操作是對word1插入1個字符,意味著word2[j]由word1中新插入的字符對應,這是在word1[:i]和word2[:j-1]完成轉換基礎上增加一次插入操作實現,即dist[i][j] = dist[i][j-1] + 1
(3)替換,最后操作是對word1替換1個字符,意味著word1[i]替換成word2[j]后實現兩單詞匹配,即在word1[:i-1]和word2[:j-1]完成轉換基礎上增加一次替換操作實現,即dist[i][j] = dist[i-1][j-1] + 1
那么我們應該選擇一種操作,使得 dp[i] [j] 的值最小,顯然有
過程如圖3所示
第一行,是 word1 為空變成 word2 最少步數,就是插入操作
第一列,是 word2 為空,需要的最少步數,就是刪除操作
步驟三、設定初始值:
顯然,當 dist[i] [j] 中,如果 i 或者 j 有一個為 0,那么還能使用關系式嗎?答是不能的,因為這個時候把 i - 1 或者 j - 1,就變成負數了,數組就會出問題了,所以我們的初始值是計算出所有的 dist[0] [0….n] 和所有的 dist[0….m] [0]。
對于邊界情況,一個空串和一個非空串的編輯距離為 D[i][0] = i 和 D[0][j] = j,D[i][0] 相當于對 word1 執行 i 次刪除操作,D[0][j] 相當于對 word1執行 j 次插入操作。
步驟四、狀態壓縮:
實際上,定義了dist矩陣后,發現每個方格距離僅與其左、上、左上三個值有關,進而又可以僅定義一個一維距離列表和一個輔助列表實現記錄,從而優化空間復雜度.
這道題中,不能每次更新完 (i, j) 的值之后,就把 (i, j-1) 的值拋棄,也就是不能一邊更新 dp[i] 的值,一邊把 dp[i] 的舊值拋棄。以往只需要用到 (i-1, j) 和 (i, j-1)的值,但是這里還需要用到 (i-1, j-1) 這個值(但是這個值在以往的案例1 中,它會被拋棄掉)需要一個輔助列表 tmp 來時刻保存 (i-1,j-1) 的值。推導公式就可以從二維的
dist[i][j] = min(dist[i-1][j] , dist[i-1][j-1] , dist[i][j-1]) + 1轉化為一維的
dist[i] = min(dist[i-1], tmp, dist[i]) + 1。進一步地,考慮定義的三種操作構成對稱關系:在word1中刪除字符與在word2中插入字符其轉換效果是一致的,而替換更是對稱操作,從而由word1轉換為word2和由word2轉換為word1其最小編輯距離也是一致的。基于此,可根據word1和word2字符長短進一步優化空間復雜度為最小的那個維度
步驟五、選出結果:
根據狀態轉移方程,求路徑的總數,因此 dist[i] [j]表示的是最小編譯距離
def MinDistance(word1:str,word2:str):m = len(word1)n = len(word2)# 有一個字符串為空串if n*m ==0:return n+m# dist 數組dist =[[0]*(n+1) for _ in range(m+1)]# 邊界狀態初始化for i in range(m+1):dist[i][0] = ifor j in range(n+1):dist[0][j] = j# 計算所有 dist 值for i in range(1,m+1):for j in range(1,n+1):if word1[i-1] == word2[j-1]:dist[i][j] = dist[i-1][j-1]    else:dist[i][j] = min(dist[i-1][j],dist[i][j-1],dist[i-1][j-1])+1return dist[m][n]優化后:
class Solution:def minDistance(self, word1: str, word2: str) -> int:if len(word2)<len(word1):#保證word1是短單詞word1, word2 = word2, word1m, n = len(word1), len(word2)dist = list(range(m+1))#word2長度為0時,由不同長度word1轉換的編輯距離for i in range(1, n+1):tmp = [i]*(m+1)#word2長度為i時,由0長度的word1轉換的編輯距離for j in range(1, m+1):if word1[j-1] == word2[i-1]:tmp[j] = dist[j-1]else:tmp[j] = min(tmp[j-1], dist[j], dist[j-1]) + 1dist = tmpreturn dist[-1]
    
                            總結
以上是生活随笔為你收集整理的建立二维数组_二维数组的 DP的全部內容,希望文章能夠幫你解決所遇到的問題。
                            
                        - 上一篇: 魔力深邃背景值多少钱
 - 下一篇: 华字开头的成语有哪些啊?