代码随想录算法训练营第三十六天|LeetCode1049.最后一块石头的重量II、LeetCode494.目标和、LeetCode474.一和零

前言

打卡代码随想录算法训练营第49期第三十六天...φ(0￣*)啦啦啦_φ(*￣0￣)′

首先十分推荐学算法的同学可以先了解一下代码随想录，可以在B站卡哥B站账号、代码随想录官方网站代码随想录了解，卡哥清晰易懂的算法教学让我直接果断关注，也十分有缘和第49期的训练营大家庭一起进步。

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

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

文章讲解：最后一块石头的重量II

视频讲解：卡哥讲解 —— 最后一块石头的重量II

本题和上一题分割等和子集差不多。

public class Solution {
    public int LastStoneWeightII(int[] stones) {
        int sum = 0;
        foreach(var stone in stones)
            sum += stone;
        int target = sum / 2;
        //dp数组含义：容量为i的背包 能装的最大容量dp[i]
        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 - dp[target] - dp[target];
    }
}

LeetCode 494 目标和

题目链接：494 目标和

文章讲解：目标和

视频讲解：卡哥讲解 —— 目标和

本题求得是装满目标背包的方式有几种，注意题目。

public class Solution {
    public int FindTargetSumWays(int[] nums, int target) {
        int sum = 0;
        foreach(var num in nums)
            sum += num;
        if((sum + target) % 2 == 1)
            return 0;
        if(Math.Abs(target) > sum)
            return 0;
        int rTarget = (sum + target) / 2;
        //dp数组含义：装满i容量的背包 有dp[i]种方式
        int[] dp = new int[rTarget + 1];
        dp[0] = 1;
        for(int i = 0; i < nums.Length; i++)
        {
            for(int j = rTarget; j >= nums[i]; j--)
            {
                //递推公式
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[rTarget];
    }
}

LeetCode 474 一和零

题目链接：474 一和零

文章讲解：一和零

视频讲解：卡哥讲解 —— 一和零

本题依然是01背包，只不过要填满二维内容。

public class Solution {
    public int FindMaxForm(string[] strs, int m, int n) {
        //dp数组含义：装满m个0和n个1的背包 需要的数量dp[m][n]
        int[][] dp = new int[m + 1][];
        for(int i = 0; i < m + 1; i++)
            dp[i] = new int[n + 1];
        foreach(var str in strs)
        {
            int zero = 0;
            int one = 0;
            foreach(var c in str)
            {
                if(c == '0')
                    zero++;
                else
                    one++;
            }
            for(int i = m; i >= zero; i--)
                for(int j = n; j >= one; j--)
                    dp[i][j] = Math.Max(dp[i][j] , dp[i -zero][j - one] + 1);
        }
        return dp[m][n];

    }
}

今天的题目很难，往后也会很难，加油！！！明天见~~~