前置知识: 讲解067、讲解068 - 二维动态规划及其空间压缩技巧 讲解073 - 01背包、有依赖的背包 【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

分组背包：多个物品分组，每组只能取1件 每一组的物品都可能性展开就可以了。注意时间复杂度不会升阶，O(物品数量 * 背包容量)

完全背包：与01背包的区别仅在于 每种商品可以选取无限次。时间复杂度O(物品数量 * 背包容量)

题目1 分组背包(模版) 给定一个正数m表示背包的容量，有n个货物可供挑选 每个货物有自己的体积(容量消耗)、价值(获得收益)、组号(分组) 同一个组的物品只能挑选1件，所有挑选物品的体积总和不能超过背包容量 怎么挑选货物能达到价值最大，返回最大的价值 测试链接 : https://www.luogu.com.cn/problem/P1757

题目2 从栈中取出K个硬币的最大面值和 一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币 每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里 给你一个列表 piles ，其中 piles[i] 是一个整数数组 分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k 请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少 测试链接 : https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/

题目3 完全背包(模版) 给定一个正数t，表示背包的容量 有m种货物，每种货物可以选择任意个 每种货物都有体积costs[i]和价值values[i] 返回在不超过总容量的情况下，怎么挑选货物能达到价值最大 返回最大的价值 测试链接 : https://www.luogu.com.cn/problem/P1616

题目4 正则表达式匹配 给你字符串s、字符串p s中一定不含有'.'、''字符，p中可能含有'.'、''字符 '.' 表示可以变成任意字符，数量1个 '' 表示可以让 '' 前面那个字符数量任意(甚至可以是0个) p中即便有''，一定不会出现以''开头的情况，也一定不会出现多个''相邻的情况(无意义) 请实现一个支持 '.' 和 '' 的正则表达式匹配 返回p的整个字符串能不能匹配出s的整个字符串 测试链接 : https://leetcode.cn/problems/regular-expression-matching/

题目5 通配符匹配（和题目4高度相似，只是边界条件不同而已，而且更简单） 给你字符串s、字符串p s中一定不含有'?'、''字符，p中可能含有'?'、''字符 '?' 表示可以变成任意字符，数量1个 '' 表示可以匹配任何字符串 请实现一个支持 '?' 和 '' 的通配符匹配 返回p的整个字符串能不能匹配出s的整个字符串 测试链接 : https://leetcode.cn/problems/wildcard-matching/

题目6 购买足量干草的最小花费 有n个提供干草的公司，每个公司都有两个信息 cost[i]代表购买1次产品需要花的钱 val[i]代表购买1次产品所获得的干草数量 每个公司的产品都可以购买任意次 你一定要至少购买h数量的干草，返回最少要花多少钱 测试链接 : https://www.luogu.com.cn/problem/P2918

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com