474. 一和零

在計算機界中，我們總是追求用有限的資源獲取最大的收益。

現在，假設你分別支配著 m 個 0 和 n 個 1。另外，還有一個僅包含 0 和 1 字符串的數組。

你的任務是使用給定的 m 個 0 和 n 個 1 ，找到能拼出存在于數組中的字符串的最大數量。每個 0 和 1 至多被使用一次。

注意:

給定 0 和 1 的數量都不會超過 100。
給定字符串數組的長度不會超過 600。
示例 1:

輸入: Array = {“10”, “0001”, “111001”, “1”, “0”}, m = 5, n = 3
輸出: 4

解釋: 總共 4 個字符串可以通過 5 個 0 和 3 個 1 拼出，即 “10”,“0001”,“1”,“0” 。
示例 2:

輸入: Array = {“10”, “0”, “1”}, m = 1, n = 1
輸出: 2

解釋: 你可以拼出 “10”，但之后就沒有剩余數字了。更好的選擇是拼出 “0” 和 “1” 。

代碼

func findMaxForm(strs []string, m int, n int) int {// golang 二維數組的初始化dp := make([][]int, m + 1)for i := 0; i <= m; i++ {dp[i] = make([]int, n + 1)}// 這個題我們不能從0,0開始判斷，外循環條件是strfor _, str := range strs {// 查詢當前字符串中0和1的個數number0, number1 := getLen(str)for i := m; i >= number0; i-- {for j := n; j >= number1; j-- {dp[i][j] = max(dp[i][j], dp[i-number0][j-number1] + 1)}}}return dp[m][n] }func max(a, b int) int {if a > b {return a}return b }func getLen(str string) (number0, number1 int) {for _, n := range str {if n == '0' {number0++} else {number1++}}return number0, number1 } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的474. 一和零 golang动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。