LeetCode:一和零_474

思路

多维的动态规划,属于背包类问题,只是穷举多了个背包。

strs里的每个元素就是物品,m为装1的背包数量,n为装0的背包数量,开始DP套路:

定义状态:dp[i][m][n]表示0-i个物品,m个装1的背包,n个装0的背包可以装下多少个物品
状态转移方程:dp[i][m][n]=max(dp[i-1][m][n],dp[i-1][m-i1][n-i0]+1)
初始值:dp[0][m][n]=0

优化

由于dp[i][m][n]的取值都来源于dp[i-1][m][n],那么可以直接用二维数组,只是每次放物品时,都在同一个二维数组上操作,也就是基于上一个物品的二维数组计算。这就是滚动数组的由来,需要满足的条件是:上一层可以重复利用,直接拷贝到当前层。

正序遍历背包数量时,三维数组用到了dp[i-1][m-i1][n-i0],现在是dp[m-i1][n-i0],因为是正序,所以这个值是在dp[m][n]计算前就计算过了,也就是被覆盖了,不再等于dp[i-1][m-i1][n-i0]。而后序遍历可以正常计算,计算dp[m][n]时,dp[m-i1][n-i0]还没使用过,就是之前的值。

题目

代码

func findMaxFormOld(strs []string, m int, n int) int {
    dp := iniDpArr(strs, m, n)
    for i, str := range strs {
        zeroCount, oneCount := countOfZeroAndOne(str)
        // 当前物品固定,穷举背包数量
        for j := 0; j <= m; j++ {
            for k := 0; k <= n; k++ {
                // 装不下该物品 = 不装
                if j < zeroCount || k < oneCount {
                    dp[i+1][j][k] = dp[i][j][k]
                } else {
                    dp[i+1][j][k] = max(dp[i][j][k], dp[i][j-zeroCount][k-oneCount]+1)
                }
            }
        }
    }
    return dp[len(strs)][m][n]
}

// 优化后
func findMaxForm(strs []string, m int, n int) int {
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for _, s := range strs {
        zeros := strings.Count(s, "0")
        ones := len(s) - zeros
        for j := m; j >= zeros; j-- {
            for k := n; k >= ones; k-- {
                dp[j][k] = max(dp[j][k], dp[j-zeros][k-ones]+1)
            }
        }
    }
    return dp[m][n]
}

func countOfZeroAndOne(str string) (int, int) {
    var zeroCount, oneCount int
    for _, char := range str {
        if '0' == char {
            zeroCount++
        } else if '1' == char {
            oneCount++
        }
    }
    return zeroCount, oneCount
}

func iniDpArr(strs []string, m int, n int) [][][]int {
    var dp = make([][][]int, len(strs)+1)
    for i := range dp {
        dp[i] = make([][]int, m+1)
        for j := range dp[i] {
            dp[i][j] = make([]int, n+1)
        }
    }
    return dp
}

func max(i int, i2 int) int {
    if i > i2 {
        return i
    }
    return i2
}

动态规划:关于01背包问题,你该了解这些!(滚动数组)

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇