Day 43

这篇具有很好参考价值的文章主要介绍了Day 43。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Day 43

1049.最后一块石头的重量II

本题中,石头的重量是 stones[i],石头的价值也是 stones[i] ,可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]”

dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

最后dp[target]里是容量为target的背包所能背的最大重量。

那么分成两堆石头,一堆石头的总重量是dp[target],另一堆就是sum - dp[target]。

在计算target的时候,target = sum / 2 因为是向下取整,所以sum - dp[target] 一定是大于等于dp[target]的

那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        dp = [0] * 15001
        total = sum(stones)
        target = total // 2

        for stone in stones:
            for j in range(target, stone - 1, -1):
                dp[j] = max(dp[j], dp[j - stone] + stone)

        return total - dp[target] - dp[target]
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int i : stones) {
            sum += i;
        }
        int target = sum >> 1;
        //初始化dp数组
        int[] dp = new int[target + 1];
        for (int i = 0; i < stones.length; i++) {
            //采用倒序
            for (int j = target; j >= stones[i]; j--) {
                //两种情况,要么放,要么不放
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - 2 * dp[target];
    }
}
494.目标和

本题要如何使表达式结果为target,

既然为target,那么就一定有 left组合 - right组合 = target。

left + right = sum,而sum是固定的。right = sum - left

公式来了, left - (sum - left) = target 推导出 left = (target + sum)/2 。

target是固定的,sum是固定的,left就可以求出来。

此时问题就是在集合nums中找出和为left的组合。

此时问题就转化为,装满容量为x的背包,有几种方法

dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法

只要搞到nums[i],凑成dp[j]就有dp[j - nums[i]] 种方法。

例如:dp[j],j 为5,

  • 已经有一个1(nums[i]) 的话,有 dp[4]种方法 凑成 容量为5的背包。
  • 已经有一个2(nums[i]) 的话,有 dp[3]种方法 凑成 容量为5的背包。
  • 已经有一个3(nums[i]) 的话,有 dp[2]中方法 凑成 容量为5的背包
  • 已经有一个4(nums[i]) 的话,有 dp[1]中方法 凑成 容量为5的背包
  • 已经有一个5 (nums[i])的话,有 dp[0]中方法 凑成 容量为5的背包

那么凑整dp[5]有多少方法呢,也就是把 所有的 dp[j - nums[i]] 累加起来。文章来源地址https://www.toymoban.com/news/detail-646020.html

dp[j] += dp[j - nums[i]]
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if abs(target) > total:
            return 0

        if (target + total) % 2 == 1:
            return 0

        tar_sum = (target + total) // 2

        dp = [0] * (tar_sum + 1)

        dp[0] = 1
        for num in nums:
            for j in range(tar_sum, num - 1, -1):
                dp[j] += dp[j - num]
        
        return dp[tar_sum]
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) sum += nums[i];
	//如果target过大 sum将无法满足
        if ( target < 0 && sum < -target) return 0;
        if ((target + sum) % 2 != 0) return 0;
        int size = (target + sum) / 2;
        if(size < 0) size = -size;
        int[] dp = new int[size + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = size; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[size];
    }
}
474.一和零
class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for s in strs:
            zeronum = s.count('0')
            onenum = s.count('1')

            for i in range(m, zeronum - 1, -1):
                for j in range(n, onenum - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zeronum][j - onenum] + 1)

        return dp[m][n]

到了这里,关于Day 43的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 如何手机搜学法减分答案? #媒体#职场发展

    今天分享拥有拍照搜题、文字搜题、语音搜题、多重搜题等搜题模式,可以快速查找问题解析,加深对题目答案的理解。 1.证件照全能管家(APP) 一个非常好用的证件照APP 常用的证件照尺寸和底色都有、日常的证件照编辑完全够用,支持一键智能拍摄证件照,还可以对照片

    2024年02月19日
    浏览(47)
  • 【职业人生】如何有效的在职场当中避免工作失误和提高个人发展

         《左传·宣公二年》:“人谁无过,过而能改,善莫大焉。”古往今来,多少人犯过错误。强大如“智绝”的诸葛孔明,也有街亭之失。职场人更是难免会在工作中出现失误。     在职场生涯当中避免不了在工作当中带来的失误,在这过程当中,我们应当要学会怎么去

    2024年02月08日
    浏览(44)
  • [office] excel成绩表格数据排名次的教程 #职场发展#知识分享#媒体

    excel成绩表格数据排名次的教程 Excel 中经常需要使用到 排名 次的技巧,成绩表格数据具体该如何排名呢?接下来是小编为大家带来的excel成绩表格数据排名次的教程,供大家参考。 步骤1:不管在学校还是各个统计领域,排名应用随处可见,如果排序会打乱原有次序,那么好多

    2024年02月21日
    浏览(40)
  • 算法练习Day26 (Leetcode/Python-贪心算法)

    122. Best Time to Buy and Sell Stock II You are given an integer array  prices  where  prices[i]  is the price of a given stock on the  ith  day. On each day, you may decide to buy and/or sell the stock. You can only hold  at most one  share of the stock at any time. However, you can buy it then immediately sell it on the  same day . Find and return 

    2024年02月03日
    浏览(43)
  • 突破职场竞争,引领未来发展:考取《研发效能(DevOps)工程师职业技术认证》

    就业形势堪忧,什么最有保障?考个“国家级”证书傍身吧! 工信部教考中心作为中国领先的行业技能认证机构,其颁发的认证证书不仅代表了个人在信息技术领域的专业能力,更可以录入工业和信息化技术技能人才数据库,这是一个重要的信息资源平台,它可以帮助企业和

    2024年02月05日
    浏览(47)
  • 算法练习 Day38 | LeetCode509,70,746

    先导知识: 1、动态规划常见题型 动态规划基础问题 背包问题 打家劫舍 股票问题 子序列问题 2、动态规划五部曲 (1)确定dp数组的定义及下标的含义 (2)确定递推公式 (3)dp数组如何初始化 (4)遍历顺序 (5)打印dp数组 LeetCode509:509. 斐波那契数 题目描述: 斐波那契

    2024年02月21日
    浏览(41)
  • [office] Excel中函数进行计算两个日期参数差值的方法 #职场发展#学习方法#媒体

    Excel中函数进行计算两个日期参数差值的方法 在excel使用中,如果想计算两个日期参数的差值,该用什么函数和如何使用呢?今天,小编就教大家在Excel中函数进行计算两个日期参数差值的方法。 Excel中函数进行计算两个日期参数差值的步骤 在excel中计算两个日期参数的差值,

    2024年02月20日
    浏览(49)
  • 算法练习Day30 (Leetcode/Python-动态规划)

    62. Unique Paths There is a robot on an  m x n  grid. The robot is initially located at the  top-left corner  (i.e.,  grid[0][0] ). The robot tries to move to the  bottom-right corner  (i.e.,  grid[m - 1][n - 1] ). The robot can only move either down or right at any point in time. Given the two integers  m  and  n , return  the number of possible

    2024年01月20日
    浏览(43)
  • Day 43

    Day 43 1049.最后一块石头的重量II 本题中,石头的重量是 stones[i],石头的价值也是 stones[i] ,可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]” dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]); 最后dp[target]里是容量为target的背包所能背的最大重量。 那么分成两堆石头,一

    2024年02月13日
    浏览(79)
  • 【DAY43-2】前端知识整理

    HTML : 超链接标签 :a href=\\\"\\\"内容/a href:链接地址,可以是内部链接,也可以是内部链接 跳转到超链接设置的锚的位置的语法:a href=\\\"#锚名\\\" HTML表格: table表格 tr行 td单元格 单行文本域: form         input type=\\\"text\\\" name=...... /form 密码框 :type=“password\\\" 文件域 :type=\\\"file\\\" 单选框

    2023年04月22日
    浏览(80)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包