《算法集训传送门》

  👉引言

---

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

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

---

今日主题：完全背包问题

---

从暴力递归的角度来讲，完全背包类的动态规划问题 其实就是 含有for遍历的回溯问题，类似于 每种面值的纸币无限张，寻找得到指定金额的最小纸币数量， 总的来说 还是暴力递归开始，一般优化到记忆化搜索就可以，但是对于有些题可能会 TLE，可以进行 斜率优化，四边形不等式优化，剪枝策略等等

 👉⭐️第一题💎

   ✨题目

      322. 零钱兑换 - 力扣（LeetCode）

   ✨思路：

首先想出暴力求解法，即将所有情况列举一遍，然后找出符合要求中的最小值。然后创建一个备忘录(dp)将已经求出的子问题的解存起来，下一次直接使用，无需重新计算

   ✨代码：

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}


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

 👉⭐️第二题💎

   ✨题目

      518. 零钱兑换 II - 力扣（LeetCode）

   ✨思路：

思路

   ✨代码：

class Solution {
    public int change(int amount, int[] coins) {


        int[][] dp = new int[coins.length + 1][amount + 1];

        for(int i = 0; i < dp.length; i ++) {
           dp[i][0] = 1;
        }
        for(int i = 0; i < dp[0].length; i ++) {
            dp[0][i] = 0;
        }

        for(int i = 1; i < dp.length; i ++) {
            for(int j = 1; j < dp[0].length; j ++) {
                //由于多了一列，coins的下标需要减一
                if(j < coins[i-1]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }
            }
        }

        return dp[coins.length][amount];
    }
}


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

 👉⭐️第三题💎

   ✨题目

      1449. 数位成本和为目标值的最大数字 - 力扣（LeetCode）

   ✨思路：

思路

   ✨代码：

class Solution {
public:
   int cost[9 + 5];
   string dp[9 + 5][5000 + 5];
   // 返回两者较大的一个
   string string_max(const string &lhs, const string &rhs) {
       if (lhs.size() > rhs.size()) return lhs;
       if (rhs.size() > lhs.size()) return rhs;
       // 当两字符串长度相等时
       if (lhs > rhs) return lhs;
       else return rhs;
   }
   string largestNumber(vector<int>& c, int target) {
       int len = c.size();
       for (int i = 0; i < len; ++i) {
           cost[i + 1] = c[i];
       }
       // dp[i][j]表示前i个元素, 恰好构成成本为j时, 构成的最大的整数(整数用字符串表示)
       // 无效状态用'#'表示
       for (int j = 0; j <= target; ++j) {
           dp[0][j] = '#';
       }
       dp[0][0] = "";
       for (int i = 1; i <= 9; ++i) {
           for (int j = 0; j <= target; ++j) {
               string a, b;
               // 不选第i个
               a = dp[i - 1][j];
               // 加选一个
               if (j - cost[i] >= 0 && dp[i][j - cost[i]] != "#")
                   b = std::to_string(i) + dp[i][j - cost[i]];
               dp[i][j] = string_max(a, b);
           }
       }
       if (dp[9][target] == "#") return "0";
       else return dp[9][target];
   }
};


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
33
34
35
36
37
38
39
40

---

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