最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

【算法训练营day43】LeetCode1049. 最后一块石头的重量II LeetCode494. 目标和 LeetCode474. 一和零

来源：博客园

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

题目链接：1049. 最后一块石头的重量II


(相关资料图)

独上高楼，望尽天涯路

一开始还是没有想到怎么转化成01背包问题，所以直接看题解找思路

慕然回首，灯火阑珊处

本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

class Solution {public:    int lastStoneWeightII(vector& stones) {        if (stones.size() == 1) return stones[0];        int sum_stones = 0;        for (int stone : stones) {            sum_stones += stone;        }        int bag_weight = sum_stones / 2;        vector dp(bag_weight + 1, 0);        for (int i = 0; i < stones.size(); i++) {            for (int j = bag_weight; j >= stones[i]; j--) {                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);            }        }        return sum_stones - 2 * dp[bag_weight];    }};

LeetCode494. 目标和

题目链接：494. 目标和

独上高楼，望尽天涯路

卡在这个问题上好几天了，看了题解的递推公式也没有想明白。

慕然回首，灯火阑珊处

首先应该想到的是如何转化成背包问题。

如何转化为01背包问题呢

假设加法的总和为x，那么减法对应的总和就是sum - x

所以我们要求的是 x - (sum - x) = target

x = (target + sum) / 2

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

dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法

递推公式用二维dp数组表示出来更容易理解，和之前背包问题的思路一样，无非是对于第i件物品有放进背包和不放进背包两种情况，现在要统计的是装满背包一共有多少种方法，只需要将这两种情况的方法数加起来，就是考虑0到i物品的总方法数，即dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]，化简为一维dp数组滚动表示后才是代码中的递推公式。

最后考虑一维dp数组的初始化，首先dp[0]一定要是1，可以理解为对于没有空间的背包，本身也是一种装满的状态，如果dp[0]不是1的话，dp数组后面所有的元素就都为0了。

class Solution {public:    int findTargetSumWays(vector& nums, int target) {        int sum_nums = 0;        for (int i = 0; i < nums.size(); i++) sum_nums += nums[i];        if ((target + sum_nums) % 2 == 1) return 0;        if (abs(target) > sum_nums) return 0;        int bag_size = (target + sum_nums) / 2;        vector dp(bag_size + 1, 0);        dp[0] = 1;        for (int i = 0; i < nums.size(); i++) {            for (int j = bag_size; j >= nums[i]; j--) {                dp[j] += dp[j - nums[i]];            }        }        return dp[bag_size];    }};

LeetCode474. 一和零

题目链接：474. 一和零

独上高楼，望尽天涯路

本题不过是一个二维空间的01背包，用经典的解法即可。

class Solution {public:    int findMaxForm(vector& strs, int m, int n) {        vector> dp(m + 1, vector (n + 1, 0));        for (int i = 0; i < strs.size(); i++) {            int zeros = 0;            int ones = 0;            for (int l = 0; l < strs[i].size(); l++) {                if (strs[i][l] == "0") zeros++;                else ones++;            }            for (int j = m; j >= zeros; j--) {                for (int k = n; k >= ones; k--) {                    dp[j][k] = max(dp[j][k], dp[j - zeros][k - ones] + 1);                }            }        }        return dp[m][n];    }};

慕然回首，灯火阑珊处

思路完全一样。

本题中strs 数组里的元素就是物品，每个物品都是一个！

而m 和 n相当于是一个背包，两个维度的背包。

关键词： 望尽天涯路 独上高楼 灯火阑珊处