474. 一和零 - Kotlin 0-1背包DP问题

原题地址：https://leetcode.cn/problems/ones-and-zeroes/description/

题解

0-1背包问题

• 其中m和n分别为两个背包，而字符串中0和1的个数对应一个物品的两个属性
• 只有当m-count(0)和n-count(1)都满足大于等于0时，这个物品才能被加进背包里

由于这题的物品放入顺序并不重要，因此属于求组合情况，应当外层遍历物品，内层遍历背包

在遍历物品时，若正序遍历DP数组，后遍历到的情况会考虑到前面的情况，而正序遍历的情况下前面的情况已经考虑到了将该物品加入背包，此时后遍历的情况如果再次选择将物品加入背包，则会导致同一个物品被重复选择，与题意不符

考虑到后效性的问题：即一个物品被选择后，后面就不能再选择该物品，本题应当采用逆序DP的遍历方式

时间复杂度：O(mnj)

空间复杂度：O(m*n+j)

class Solution {
    fun findMaxForm(strs: Array<String>, m: Int, n: Int): Int {
        val items=Array(strs.size){ intArrayOf(0,0) }
        for((index,str) in strs.withIndex()){
            for(chr in str){
                when(chr){
                    '0'-> items[index][0]++
                    '1'-> items[index][1]++
                }
            }
        }

        val dp=Array(m+1){Array(n+1){0} }
        for(item in items){
            for(i in m downTo 0){
                for(j in n downTo 0){
                    if(i-item[0]>=0&&j-item[1]>=0){
                        dp[i][j]=Math.max(dp[i][j],dp[i-item[0]][j-item[1]]+1) 
                    }
                }
            }
        }
        return dp[m][n]
    }
}