《算法集训传送门》

  👉引言

---

💖 ❄️我们的算法之路❄️💖

   众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
              ☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
   💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs)，💝宽度优先搜索（bfs），💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉

---

今日主题：01背包问题

---

 👉⭐️第一题💎

   ✨题目

      416. 分割等和子集 - 力扣（LeetCode）

   ✨思路：

动态规划，建议从暴力递归开始想，而不是直接推状态转移方程，做多了自然也就能直接想到状态转移了，这里直接给出打表代码

   ✨代码：

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        Sum, Max, target, n= sum(nums), max(nums), sum(nums)//2, len(nums)
        if Sum%2==1: return False
        if Max > target: return False

        dp = [[False]*(target+1) for i in range(n)]
        dp[0][nums[0]] = True
        for i in range(n):
            dp[i][0] = True
        
        for i in range(n):
            for j in range(1, target+1):
                if j>=nums[i]: dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]
                else: dp[i][j] = dp[i-1][j]
        return dp[n-1][target]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

 👉⭐️第二题💎

   ✨题目

      494. 目标和 - 力扣（LeetCode）

   ✨代码：

    public static int findTargetSumWays(int[] nums, int s) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        // 绝对值范围超过了sum的绝对值范围则无法得到
        if (Math.abs(s) > Math.abs(sum)) return 0;

        int len = nums.length;
        // - 0 +
        int t = sum * 2 + 1;
        int[][] dp = new int[len][t];
        // 初始化
        if (nums[0] == 0) {
            dp[0][sum] = 2;
        } else {
            dp[0][sum + nums[0]] = 1;
            dp[0][sum - nums[0]] = 1;
        }

        for (int i = 1; i < len; i++) {
            for (int j = 0; j < t; j++) {
                // 边界
                int l = (j - nums[i]) >= 0 ? j - nums[i] : 0;
                int r = (j + nums[i]) < t ? j + nums[i] : 0;
                dp[i][j] = dp[i - 1][l] + dp[i - 1][r];
            }
        }
        return dp[len - 1][sum + s];
    }


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
32

 👉⭐️第三题💎

   ✨题目

      879. 盈利计划 - 力扣（LeetCode）

   ✨代码：

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        l = len(group)
        t = sorted([[group[i], profit[i]] for i in range(l)])
        @lru_cache(None)
        def dfs(i, c, s):
            if i == l or t[i][0] > c:
                return 1 if s == minProfit else 0
            return (dfs(i + 1, c, s) + dfs(i + 1, c - t[i][0], min(minProfit, s + t[i][1]))) % mod
        mod = 10 ** 9 + 7
        return dfs(0, n, 0)


1
2
3
4
5
6
7
8
9
10
11
12
13

---

🌹写在最后💖：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！🌹🌹🌹