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

文章：14. 最后一块石头的重量II

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

【题目】

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；

如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

【思路】

本题的题意：尽量将石头分成重量相等的两堆，返回这两堆的差值

1.确认数组及其下标含义

dp[i]：在背包的重量为i时，dp[i]为物品的最大价值（能背的最大重量）

2.确认递推公式

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

3.数组初始化

题目数值为正整数，非零下标初始化为0即可。

dp[0] = 0

4.确定遍历顺序

因为本题我们使用的是01背包，因此需要先遍历物品，然后再遍历背包容量且倒序！

5.举例推导

…

  • java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int lastStoneWeightII(int[] stones) {
        //该题的主要思想：尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小 ==》转化为01背包
        //所以target == weight/2 
        int sum = 0;
        for(int i = 0 ; i < stones.length;i++){
            sum += stones[i];
        }
        int target = sum/2;
        //1.确认dp及其下标含义 dp[i] : 下标为i时dp[i]的重量最大
        int[]dp = new int[target+1];//重量最大为30*1000，分两组
        //2.确认递推公式 dp[j] = min(dp[j],dp[j-stones[i]]+stone[i]) 
        //3.初始化dp数组
        dp[0] = 0;
        //01背包，内循环倒序！
        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 - dp[target]-dp[target];
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func lastStoneWeightII(stones []int) int {
    sum := 0
    for i := range stones{
        sum += stones[i]
    }
    target := sum/2
    dp := make([]int,target+1)
    for i:=0;i< len(stones);i++{
        for j := target;j>= stones[i];j--{
            dp[j] = max(dp[j],dp[j-stones[i]]+stones[i])
        } 
    }
    //总的重量减去两倍的dp[target]即得出最小差值！！！
    return sum-dp[target]-dp[target]
}

494.目标和

文章：16. 目标和

题目：494. 目标和

【思路】

使用两个集合：加法的集合、减法的集合

加法的集合(left) - 减法的集合（right）= target

left + right = sum

right = sum-left

left - (sum-left) = target

2left - sum = target（sum、target是固定的）

因此 left = (sum+target)/2

本题转化为 =》 有多少个集合可以装满left容量的背包（01背包）

1.确认数组及其下标含义

dp[j]：容量为j，装满j容量的方法有dp[j]种

2.递推公式推导

dp[j] += dp[j - nums[i]]

3.数组初始化

由于本题的递推公式是累加（初始化为0的话整个数组都是0了） && 容量为0时，什么都不去也可以看作一种方法 ==》dp[0] = 1

题目提供的都是正整数，因此非零下标初始化为0即可

4.确认遍历顺序

01背包，先遍历物品，再遍历背包且倒序

5.举例推导

。。。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //本题需要如何使表达式结果为target
        //有target 就一定有left和right组合。已知jsum + jneg = sum,且jsum - jneg = target 
        //===> jsum + target + jsum = sum => jsum = (sum -target)/2
        int sum = 0 ; 
        for(int i = 0 ; i < nums.length;i++){
            sum += nums[i];
        }
        //go语言要另外转换
        if(sum < target)return 0;
        if( (sum+target) %2 == 1)return 0;
        //0.确定是哪个背包 每个数字只能用一次 01背包
        //1.确定dp及其下标含义  dp[i] : 下标为i时有最多dp[i]种方案
        int bagsize = (sum-target)/2;

        int[]dp = new int[bagsize+1];
        //2.确认递推公式 该题目有个特点：dp[i]都会依赖前面的dp[i-1]的结果进行累加
        //==> dp[j] += dp[j-nums[i]]
        //
        //3.数组初始化 dp[0] 有最多1 种解决方案
        dp[0] = 1;
        //4.确认遍历顺-序  内循环倒序！
        for(int i = 0 ; i < nums.length ;i++){
            for(int j = bagsize ; j >= nums[i];j--){
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[bagsize];
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func findTargetSumWays(nums []int, target int) int {
    sum := 0
    //又犯了相同的错误！
    for _,i := range nums{
        sum += i
    }
    //为了过nums=[100],target=-200,避免出现target > sum的无效情况
    if abs(target) > sum{
        return 0
    }

    if abs(target) >sum{
        return 0
    }
    if (sum + target) %2 == 1{
        return 0
    }
    left:= (sum+target)/2
    dp := make([]int,left+1)
    dp[0] =1
    for i := 0 ;i < len(nums);i++{
        for j := left;j >= nums[i];j--{
            dp[j] += dp[j-nums[i]]
        }
    }
    return dp[left]
}
func abs(x int)int{
    return int(math.Abs(float64(x)))
}

474.一和零

文章：17. 一和零

题目：474. 一和零

【思路】

本题的物品只能用一次 =》01背包

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

1.确定dp数组及其下标的含义

dp[i] [j]：最多有i个0和j个1的strs的最大子集的大小为dp[i] [j]

2.确定递推公式

dp[i] [j]可以由前一个strs里的字符串推导出来，strs的字符串里有zeroNum个0，oneNum个1

dp[i] [j]就可以是dp[i - zeroNum] [j - oneNum]+1

然后在遍历的过程中取dp[i] [j] 的最大值

字符串的zeroNum和oneNum相当于物品的重量weight[i]，而字符串本身的个数就相当于物品的价值value[i]

=》递推公式：dp[i] [j] = max(dp[i] [j],dp[i - zeroNum] [j - oneNum]+1（物品有两个维度）

3.dp数组如何初始化

本题中物品的价值为正整数，因此非零下标的数值初始化为0即可

4.确定遍历顺序

01背包，先遍历物品，然后再遍历背包且倒序

5.举例推导

。。。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //0.每个元素只能用一次，所以是 01背包，也就意味着内循环需要倒序遍历
        //1.确认dp数组以及其下标的含义：dp[i][j]:最多有i个0和j个1 的最大子集为dp[i][j]
        //2.确认递推公式
        //dp[i][j]可由前一个strs数组得出：dp[i][j] = max(dp[i][j],dp[i-zeroNum][j-oneNum] + 1)
        
        int[][]dp = new int[m+1][n+1];
        for(String str : strs){
            int zeroNum =0;
            int oneNum =0;   
            for(int i = 0 ; i < str.length();i++){
                char c = str.charAt(i);
                if(c == '0')zeroNum++;
                if(c == '1')oneNum++;
            }
            for(int i = m ; i>= zeroNum;i--){
                for(int j = n;j >= oneNum;j--){
                    dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum]+1);
                }
            }
        }
        return dp[m][n];

    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func findMaxForm(strs []string, m int, n int) int {
    dp := make([][]int,m+1)
    for i,_:=range dp{
        dp[i] = make([]int,n+1)
    }
    for i:=0 ;i < len(strs);i++{
        zeroNum ,oneNum := 0,0
        //str每个项里面都是字符串，遍历str不单止，还需要遍历str[i]，才能求出里面的0和1
        for _, num := range strs[i]{
            if num =='0'{
                zeroNum++
            }
        }
        oneNum = len(strs[i]) - zeroNum
        for a1 := m;a1 >= zeroNum;a1--{
            for a2 :=n;a2>=oneNum;a2--{
                dp[a1][a2] = max(dp[a1][a2],dp[a1 - zeroNum][a2 -oneNum]+1)
            }
        }
    }
    return dp[m][n]
}
func maxa(a,b int)int{
    if a > b{
        return a
    }
    return b
}

【算法总结】

  • 最后一块石头的重量II：使用01背包，思路是将石头尽可能分成重量相等的两份，实践是将石头总重量的一半当作背包的最大容量，单个石头的重量作为物品的价值，循环遍历比较得到最大值。然后将总重量减去两份的背包最大值即可得出石头的重量差值。
  • 目标和：使用01背包，思路是将目标和以及数组的加法集合、减法集合、数组总和凑出一条等式，通过求取加法集合（或减法集合）的最大价值获得凑到该最大价值有多少种方法，因此是采用累加的方式来得到最大价值。
  • 一和零：使用01背包，思路是将0和1看作两个维度的背包，将str字符串数组看作物品。因为有两个维度上的背包，因此我们需要使用二维数组进行循环且背包维度倒序遍历。

【语言总结】

  • Go语言

二维数组初始化不够熟练、对字符串的循环遍历不够熟练。