leetcode:474.一和零

解题思路:

背包(即最终结果数组包含有m个0和n个1)容量有两个维度,m个0和n个1,最终结果含有的元素个数相当于物品个数。

由于每个物品只能使用1次,所以这依然是个01背包问题。本题是求解装满这个背包最多有多少个物品。

dp数组含义:dp[i][j]表示在i个0,j个1的情况下,最多背dp[i][j]个物品,最后结果是dp[m][n].

递推公式:dp[i][j] = max(dp[i-x][j-y] + 1,dp[i][j])

初始化:dp[0][0] = 0,非0下标初始化成0(由递推公式得)

遍历顺序:先物品再背包(倒序),这里背包容量是二维的。

代码实现:

相关推荐

  1. Leetcode 474

    2024-02-22 03:34:01       30 阅读
  2. LeetCode 474.

    2024-02-22 03:34:01       12 阅读
  3. 动态规划 Leetcode 474

    2024-02-22 03:34:01       20 阅读
  4. 474. (力扣LeetCode

    2024-02-22 03:34:01       17 阅读
  5. 474.

    2024-02-22 03:34:01       20 阅读

最近更新

  1. TCP协议是安全的吗?

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

    2024-02-22 03:34:01       16 阅读
  3. 【Python教程】压缩PDF文件大小

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

    2024-02-22 03:34:01       18 阅读

热门阅读

  1. pytroch笔记

    2024-02-22 03:34:01       32 阅读
  2. 力扣-217. 存在重复元素

    2024-02-22 03:34:01       25 阅读
  3. Rust语言之异步写文件

    2024-02-22 03:34:01       29 阅读
  4. 炫技亮点 优雅处理数据流程 过滤器模式

    2024-02-22 03:34:01       28 阅读
  5. 类和对象 下(再谈构造函数 static成员 友元)

    2024-02-22 03:34:01       32 阅读
  6. 【Linux 内核源码分析】内存管理——Slab 分配器

    2024-02-22 03:34:01       29 阅读
  7. C++面试高频问题汇总( 一)

    2024-02-22 03:34:01       36 阅读
  8. gtowizard合租cash和锦标赛mtt

    2024-02-22 03:34:01       26 阅读
  9. 前端常见面试题

    2024-02-22 03:34:01       26 阅读
  10. Qt 基本知识

    2024-02-22 03:34:01       28 阅读
  11. webrtc 中 FIR PLI 有何区别? 分别适用于什么场景

    2024-02-22 03:34:01       32 阅读
  12. vue 学习definproperty方法

    2024-02-22 03:34:01       32 阅读