Leetcode 474 一和零

题意理解

        给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

        请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。

        如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。

        

        将字符串0和1的个数看作是该字符串的两个维度,假设将其看作物品的重量和体积。

        那么m和n就是对背包的限制:承重量为m, 体积为的背包。

        求元素最多的子集,该问题可以转换为:求装满承重量m体积n的背包最多有放多少件物品。

        所以该问题被转换为一个二维的0-1背包问题。

解题思路

        首先理解题意将其转换为0-1背包问题。

        其次,此处的动态滚动数组是二维的:

        dp[i][j]表示:装满承重i,体积为j的背包最多有多少件物品。

        之前的递推公式为:

        dp[j]=max(dp[j],dp[j-weight[i]]+values[i])

        此处递推公式做些许调整:

        dp[i][j]=max(dp[i][j],dp[i-weight[i]][j-vomule[i]]+1)

        初始化:

                对于背包为0 的物品装满需要0件物品。

1.动态规划:动态滚动数组求解二维0-1背包问题

任然是采用动态规划五部曲来求解该问题,不同之处在于此处的背包是一个二维限制的背包,此处的dp滚动数组是二维的。

public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp=new int[m+1][n+1];
        for(int[] tmp:dp) Arrays.fill(tmp,0);
        int countZero=0,countOne=0;
        //遍历物品
        for(int i=0;i<strs.length;i++){
            //计算0/1个数
            countZero=0;
            countOne=0;
            for(char c:strs[i].toCharArray()){
                if(c=='0') countZero++;
                if(c=='1') countOne++;
            }
            //遍历m
            for(int w=m;w>=0;w--){
                //遍历n
                for(int v=n;v>=0;v--){
                    if(countZero<=w&&countOne<=v){
                        dp[w][v]=Math.max(dp[w][v],dp[w-countZero][v-countOne]+1);
                    }
                }
            }
        }
        return dp[m][n];
    }

2.分析

时间复杂度

        O(m×n×str_len)

空间复杂度

        O(m×n)

相关推荐

  1. Leetcode 474

    2024-01-17 13:22:02       31 阅读
  2. LeetCode 474.

    2024-01-17 13:22:02       14 阅读
  3. 动态规划 Leetcode 474

    2024-01-17 13:22:02       21 阅读
  4. 474. (力扣LeetCode

    2024-01-17 13:22:02       18 阅读
  5. 474.

    2024-01-17 13:22:02       22 阅读

最近更新

  1. TCP协议是安全的吗?

    2024-01-17 13:22:02       18 阅读
  2. 阿里云服务器执行yum,一直下载docker-ce-stable失败

    2024-01-17 13:22:02       19 阅读
  3. 【Python教程】压缩PDF文件大小

    2024-01-17 13:22:02       18 阅读
  4. 通过文章id递归查询所有评论(xml)

    2024-01-17 13:22:02       20 阅读

热门阅读

  1. 自己的第一篇博客——回顾和展望

    2024-01-17 13:22:02       35 阅读
  2. conda create SafetyError

    2024-01-17 13:22:02       35 阅读
  3. Python系列(4)—— 全局变量

    2024-01-17 13:22:02       31 阅读
  4. PHP运算符汇总

    2024-01-17 13:22:02       31 阅读
  5. vs c++ qt 打包成exe

    2024-01-17 13:22:02       33 阅读
  6. 如何理解单例模式---懒汉式?

    2024-01-17 13:22:02       30 阅读
  7. 设计模式-建造者模式

    2024-01-17 13:22:02       35 阅读