代码随想录算法训练营打卡Day43 | LeetCode1049 最后一块石头的重量 II、LeetCode494 目标和、LeetCode474 一和零

摘要

  • 用动态规划解决问题时,不仅要从简单的子问题来考虑递推公式,也要从问题的整体来考虑,看问题的输入参数本身有什么性质和公式,也有助于得到递推公式。

LeetCode1049 最后一块石头的重量 II

1049. 最后一块石头的重量 II - 力扣(Leetcode)

  • 从问题的整体来考虑,要使一堆石头两两一起“粉碎”后剩余的重量值最小,那么应该把这堆石头尽可能地分成重量相等或相近的两堆石头,分出来的两堆石头两两一起“粉碎”后剩余的重量值就是最小的重量值。注意,如果粉碎后的石头有剩余,那可以看作继续分成重量尽可能相近的两堆,然后继续让这两堆石头两两一起粉碎。
  • 将一堆石头分成两堆重量尽可能相近的石头,设石头的重量总和为sum
    • 对于石头i,要么在第一堆里,要么在第二堆里。只针对分出来的第一堆石头,石头i要么在第一堆里,要么不在,这和 0-1 背包问题对于物品的取法是一致的。
    • 两堆石头的重量要尽可能相近,所以分出来的一堆石头的重量最大值应该是sum / 2 + sum % 2
  • 那么,问题可以转化成:“从一堆石头中任取石头,每个石头要么不取,要么取一次,得到的重量值尽可能地接近sum / 2 + sum % 2”。“物品”是石头,“背包”是一堆石头,“背包”的最大容量是sum / 2 + sum % 2,“物品”的价值是stones[i],“物品”的重量也是stones[i]。设halfsum / 2 + sum % 2
  • dp数组及下标的含义:dp[j]表示的是,任取石头,得到的重量值不超过j的最大值,设dp[j]的更新次数为i,则dp[j]对应的可选的石头下标范围为0i
  • 计算完dp数组后,按上述规则取石头后第一堆的重量为dp[half],第二堆的重量为sum - dp[half],则粉碎后剩余的重量为abs(sum - dp[half] - dp[half])

题解代码如下

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        if (stones.empty()) return 0;
        if (stones.size() == 1) return stones.back();
        
        int sum = 0;
        for (auto& iter : stones) sum += iter;
        int half = sum / 2  + sum % 2;
        vector<int> dp(half + 1, 0);

        for (int i = 0; i < stones.size(); i++) {
            for (int j = half; j >= stones[i]; j--) {
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }

        return abs(sum - dp[half] - dp[half]);
    }
};

LeetCode494 目标和

494. 目标和 - 力扣(Leetcode)

  • 这道题目,从整体来看,“构造表达式”也可以看作将输入的参数分为两部分:一部分添加+号,作为被减数;另一部分添加-号,作为减数。设nums中各个整数的和为sum。设被减数为minuend(正数),减数为subtractor(正数),则两者的和为sum,两者的差为target

\begin{cases} minuend + subtractor = sum \\ minuend - subtractor = target \end{cases} \Rightarrow minuend = (sum + target) / 2

  • 通过以上推导,可以看出minuend的取法,即从nums中任取k个元素,使得选取的元素的和尽可能接近(sum+target)/2,当选取的元素的和恰好等于(sum+target)/2时,说明找到了一种使得构造的表达式的结果等于target的方案。

  • 确定dp数组及下标的含义:dp[j]为从nums中任取整数,选取的整数的和恰好为j的情况,dp[j]的更新次数对应可以选取的nums的下标范围,设dp[j]更新了i次,dp[j]对应的可选取的nums的下标范围是0i

  • 要注意的是,这道题目的dp数组的含义和之前的题目不同。

    • LeetCode1049 最后一块石头的重量、LeetCode416 分割等和子集,这两道题我们并不关心有多少种组合方式得到目标值,我们关心的是是否能得到目标值,或得到一个接近目标值的值。用 0-1 背包的语言来描述,就是想让背包尽可能地装满,或者装入的物品价值尽可能大。
    • 但 LeetCode494 目标和,除了要关心是否能得到目标值,还要知道有多少种方法得到目标值。用 0-1 背包的语言来描述,就是有多少种方法恰好能装满背包。此时再用描述背包装入的重量或价值的dp来解决题目就不合适了,dp数组应该描述的是有多少种方式能恰好装满容量为j的背包。
  • 确定递推公式,先看简单的子问题

    • 一个元素都没有选取,选取出的minuend是空集,空集只有一种,且和为0,所以dp[0]初始化为1,此时minuend中整数的和只能是0,所以当j > 0时,dp[j]初始化为0
    • nums[0]是第一个尝试选取的元素,如果选nums[0],则当j == nums[0]时,dp[j]的值为1,说明得到和为nums[0]有一种方式,就是选取nums[0]
    • 假设已经在nums[0]nums[i-1]中选取了k个数,再选取了一个整数nums[i]。那么为了使得当前选取方式的minuend中的整数的和为j,就要再从nums[0]nums[i-1]选出一个和为j - nums[i]的集合。根据dp数组的定义,从nums[0]nums[i-1]选出一个和为j - nums[i]的集合的种数就是dp[j - nums[i]]
    • 这样就可以得到递推公式,其中idp[j]的更新次数下标(从0开始),i=-1表示初始状态

dp[j] = \begin{cases} 1, & j=0 \wedge i=-1 \\ 0, & j>0 \wedge i=-1 \\ dp[j] + dp[j - nums[i]], & i \ge 0 \end{cases}

  • 初始状态已经在递推公式中写明,即dp[0]初始化为1,其他dp[j]初始化为0

  • nums={1, 1, 1, 1, 1}; target=3为例,根据minuend = (sum + target) / 2,求得minuend=4,要注意的是,有两种情况是可以直接知道答案的种数是0的:

    1. sum的绝对值小于target的绝对值,即 abs(sum) < abs(target),此时说明nums中的元素全取+或全取-都不可能得到值为target的和。
    2. sum + target不能被2整除,因为nums中都是整数,对于minuend的定义是从nums中取出的部分整数的和,所以minuend也应该是整数,如果sum + target不能被2整除,说明不存在minuend使得构造出的表达式的结果为target
  • 首先画出其二维dp数组,初始状态保存在i=-1那一行,对应没有从nums中选取任何整数

  • 确定dp[j]的遍历顺序,即更新顺序,由递推公式 dp[j] = dp[j] + dp[j - nums[i]], i \ge 0 ,可以知道dp[j]的更新依赖的是上一行的且在其左边的值,所以更新顺序应该是j从大到小,即从左到右。
  • 所以先滑动dp[4]dp[4]=dp[4]+dp[4-1]=0;
  • dp[2]dp[3]同理
  • 再看dp[1]nums[0]==1dp[1]=dp[1]+dp[1-1]=1
  • 最后看dp[0],如果j - nums[i] > 0,则dp[0]还是1,因为没有出现空集以外的集合内元素和等于0的情况。
  • 重复滑动一行的过程,把dp数组填完
  • 最后的dp[minuend]就是使得构造出的表达式的结果等于target的方法数。

题解代码如下

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (auto& iter : nums) sum += iter;
        // 直接求得方法数为 0 的情况
        if ((sum + target) % 2) return 0;
        if (abs(sum) < abs(target)) return 0;
        // 初始化 dp 数组
        int minuend = (sum + target) / 2;
        vector<int> dp(minuend + 1, 0);
        dp[0] = 1;
        // 从 i=0 开始,逐行更新 dp 数组
        for (int i = 0; i < nums.size(); i++) {
            for (int j = minuend; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }

        return dp[minuend];
    }
};

LeetCode474 一和零

474. 一和零 - 力扣(Leetcode)

  • 这道题目也是 0-1 背包问题,“物品”是集合中的元素,“背包”是子集。不过“物品”的“重量”变成了两个维度:一是“0”的个数,二是“1”的个数。题目要求子集中的元素个数最多,所以每个元素的“价值”是相等的,可以都设为1

  • 确定dp数组及数组下标的含义:dp[j][k]的含义是,从strs中任取字符串,这些字符串包含的 '0' 不超过 j 个,包含的 ’1‘ 不超过 k 个。对每个物品,dp[j][k]的值都会进行一次更新,所以依然可以省略遍历到第i个物品这个维度。

  • 递推公式,可以看出只是“重量”多了一个维度,dp[i][j][k]还是由两种可能推出:一是不放入物品i,二是放入物品i
    dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - numsOf0[i]][k - numsOf1[i]] + 1)

  • 初始化过程隐含在dp数组的计算过程中,先将dp数组全部初始化成0

  • 同样要注意dp[j][k]的更新依赖于dp[j - numsOf0[i]][k - numsOf1[i]],所以j应从大到小,k也应该从大到小。

题解代码如下

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<int> numsOf0(strs.size(), 0);
        vector<int> numsOf1(strs.size(), 0);
        for (int i = 0; i < strs.size(); i++) {
            for (auto& ch : strs[i]) {
                numsOf0[i] += ch == '0';
                numsOf1[i] += ch == '1';
            }
        }

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        for (int i = 0; i < strs.size(); i++) {
            for (int j = m; j >= numsOf0[i]; j--) {
                for (int k = n; k >= numsOf1[i]; k--) {
                    dp[j][k] = max(dp[j][k], dp[j - numsOf0[i]][k - numsOf1[i]] + 1);
                }
            }
        }

        return dp[m][n];
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,684评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,143评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,214评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,788评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,796评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,665评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,027评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,679评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 41,346评论 1 299
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,664评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,766评论 1 331
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,412评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,015评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,974评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,203评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,073评论 2 350
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,501评论 2 343

推荐阅读更多精彩内容