我正在研究在leetcode上找到的這個問題的解決方案。問題指出：給定一個數組 ，其字符串僅由0和1strs組成。還有兩個整數和。mnm現在你的任務是找到給定的0 和n 1可以組成的最大字符串數。每個0和1最多只能使用一次。輸入: strs = ["10","0001","111001","1","0"], m = 5,n = 3輸出：4解釋：用5個0和3個1可以組成4個字符串，分別是“10”、“0001”、“1”、“0”。用于解決該問題的算法如下：def findMaxForm(strs, m, n): dp = [[0] * (n + 1) for _ in range(m +1)] for s in strs: zeros, ones = s.count('0'), s.count('1') for i in range(m, zeros - 1, -1): for j in range(n, ones -1, - 1): # dp[i][j] indicates it has i zeros ans j ones, # can this string be formed with those ? dp[i][j] = max( 1 + dp[i - zeros][j - ones], dp[i][j]) # print(dp) return dp[-1][-1]問題的混亂部分是dp[i][j] = max( 1 + dp[i - zeros][j - ones], dp[i][j]). 我不確定這里發生了什么。為什么我們從 0 中減去 i，從 1 中減去 j？我還找到了一張圖表，解釋了 dp 表應該如何查找數組中的所有元素。我的問題：第一張表代表什么？x 和 y 軸？為什么有這么多1的。我想如果我理解了這一部分，可能會有所作為。如果有人瀏覽圖表，我將不勝感激為什么這種方式給了我們可以形成的最大數量的0'和1'？我想我對這部分仍然感到困惑dp[i][j] = max( 1 + dp[i - zeros][j - ones], dp[i][j])。該解決方案還被描述為“針對 2D 空間優化的 3d-DP：dp[j][k]：i 維度經過優化以就地使用。” 這意味著什么？
1 回答
HUWWW
TA貢獻1874條經驗 獲得超12個贊
遇到字符串時s，基本上有兩種選擇。它要么屬于最大解，要么不屬于。
如果這樣做，集合的大小會增加 1，但剩下的 1 和 0 會減少。如果您不使用它，集合的大小將保持不變，但如果保留 1 和 0，則數字也會保持不變。
該表dp代表了到目前為止您可以獲得的最大此類集合，用于“左”的不同數量的 1 和 0。例如。dp[m][n]表示到目前為止您可以使用m0 和n1 獲得的最佳值。同樣，對于dp[2][3]其余字符串，您可以使用 2 個零和 3 個一。
讓我們把它包裝在一起：
對于一些給定數量的零 ( i) 留下來使用，一些零 ( j) 留下來使用，以及一個字符串s：
1 + dp[i - zeros][j - ones]表示如果您決定添加到集合中的最大集合s（并且您只剩下更少的 1 和 0）dp[i][j]意味著你沒有接受這個元素，繼續前進。
當您調用max()這兩個值時，您基本上是在說：我想要這兩個選項中更好的一個。
我希望這能回答前兩個問題，即為什么它是最大的以及 dp 線的含義。
該解決方案還被描述為“針對 2D 空間優化的 3d-DP：dp[j][k]：i 維度經過優化以就地使用?！?nbsp;這意味著什么？
在這里，你有 3d 問題：你迭代的字符串本身 - 但你沒有數組的另一個維度。您將其優化為就地，因為您始終只需要前一個字符串，而不需要比它“更舊”的字符串，從而節省了寶貴的空間。
添加回答
舉報
0/150
提交
取消