首页 > 编程语言 >复习回顾-动态规划算法-474. 一和零

复习回顾-动态规划算法-474. 一和零

时间:2024-02-28 10:00:11浏览次数:38  
标签:复习 int range 算法 ones zeros 474 dp

注意点&感悟:

  • 不会,就抄一遍,默写一遍,总能会的。

题目链接:474. 一和零

自己默写的代码:

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        # 初始化
        # 外层 m个0, 内层n个1
        dp = [[0]*(n+1) for _ in range(m+1)]
        # 遍历物品
        for s in strs:
            zeros = s.count('0')    # m
            ones = s.count('1')     # n
            # 遍历背包,两个维度
            for i in range(m,zeros-1,-1):
                for j in range(n,ones-1,-1):
                    dp[i][j] = max(dp[i][j],dp[i-zeros][j-ones]+1)
        
        return dp[m][n]

通过截图:

标签:复习,int,range,算法,ones,zeros,474,dp
From: https://www.cnblogs.com/liqi175/p/18039082

相关文章

  • 逻辑回归(分类算法)
    阶跃函数Sigmoid\[g(z)=\frac{1}{1+e^{-z}}\]线性函数进行sigmoid操作\[h_{\theta}(x)=g\left(\theta^{T}x\right)=\frac{1}{1+e^{-\theta^{T}x}}\]对于分类任务\[\begin{array}{l}P(y=1\midx;\theta)=h_{\theta}(x)\\P(y=0\midx;\theta)=1-h_{\theta}(x......
  • 聚类算法
    这个算法是无监督算法,没有标签。K-MEANS算法基本概念要得到蔟的个数,需要指定K值质心:均值,向量各维度取平均值距离的度量:常用欧几里得距离和余弦相似度(先标准化)优化目标如下,\[\min\sum_{i=1}^{K}\sum_{x\inC_{i}}\operatorname{dist}\left(c_{i},x\right)^{2}\]算法......
  • day43 动态规划part5 代码随想录算法训练营 474. 一和零 【粗略理解】
    题目:474.一和零我的感悟:有点难想,加油、111本题没敲,有机会敲一遍理解难点:两个维度的背包听课笔记:代码示例:classSolution:deffindMaxForm(self,strs:List[str],m:int,n:int)->int:dp=[[0]*(n+1)for_inrange(m+1)]#创建二维动......
  • day43 动态规划part5 代码随想录算法训练营 494. 目标和
    题目:494.目标和我的感悟:加油!理解难点:dp的几种方法的应用记住dp[j]+=dp[j-nums[i]]听课笔记:代码示例:classSolution:deffindTargetSumWays(self,nums:List[int],target:int)->int:total_sum=sum(nums)ifabs(target)>total_sum:......
  • 2024牛客寒假算法基础集训营5 题解 ( A,C,G,H,I,L,M )
    2024牛客寒假算法基础集训营5题解(A,C,G,H,I,L,M)A mutsumi的质数合数题意有一个由\(n\)个正整数组成的数组,她想知道数组中质数和合数共有几个。思路由质数和合数的定义可知,正整数范围内除\(1\)外,要么是质数要么是合数,本题直接统计不是\(1\)的正整数的个数即可代码......
  • day43 动态规划part5 代码随想录算法训练营 1049. 最后一块石头的重量 II
    题目:1049.最后一块石头的重量II我的感悟:复习了昨天的模板是不一样,今天这个我推出来了。哈哈 理解难点:按照昨天的思路,dp[target]里面是能凑出来的最大值。a是另外能凑出来的和。diff是两者的差。听课笔记:我自己先写出的代码:classSolution:deflastStoneW......
  • 代码随想录算法训练营第三十天|回溯法总结
    回溯法总结回溯算法能解决如下问题:组合问题:N个数里面按一定规则找出k个数的集合排列问题:N个数按一定规则全排列,有几种排列方式切割问题:一个字符串按一定规则有几种切割方式子集问题:一个N个数的集合里有多少符合条件的子集棋盘问题:N皇后,解数独等等代码随想录(programmerc......
  • m基于深度学习的QPSK调制解调系统相位检测和补偿算法matlab仿真
    1.算法仿真效果matlab2022a仿真结果如下:  2.算法涉及理论知识概要         在数字通信中,正交相移键控(QPSK)是一种高效的调制方法,它能够在有限的带宽内传输更多的信息。然而,在实际通信过程中,由于信道噪声、多径效应等因素,接收到的QPSK信号可能会出现相位偏移,导......
  • 复习回顾-动态规划算法-416. 分割等和子集
    注意点&感悟:其实也没啥,不行就背呗~~题目链接:416.分割等和子集自己独立写的代码:classSolution:defcanPartition(self,nums:List[int])->bool:target=sum(nums)iftarget%2==1:#说明是奇数returnFalsetarget=......
  • 基础字符串算法
    1哈希1.1概念哈希就是构造一个数字使之唯一的代表一个字符串。我们来考虑一下二进制数的转化:$(1001)2=1\times23+0\times22+0\times2^1+1=(9)$现在,我们令$'a'=1,'b'=2,'c'=3\cdots,'z'=26$。然后将进制$p$设为$131$。就能得到:$(abc)p=1\timesp^2+2\timesp+3=(22483......