【C++算法入门】动态规划-糖果问题

一 原题复现

现有糖果K种，将糖果装入不同的包装，包装N种，每种包装糖果M颗。

每种包装中的糖果种类可以存在重复情况。

求如何选择包装使得在包含所有糖果种类的情况下，所选择的包装个数最少。

二 思路解析

拿到这个题目第一眼不知道从何下手，看到要求最小值，这题我们可以试着往动态规划靠拢。不妨建立一个记录拿到某几类糖果所需要的次数dp数组。此时面临的第一个问题便是怎么表示拿到了哪几个种类的糖果。试想，用多维数组，每一维表示一种糖果的状态？最好的想法是利用状态压缩，什么是状态压缩呢？就是利用01来表示某一种状态。举个例子，一共糖果5种，拿到了糖果1、2、3，那么此时的状态就是00111；如果拿到1、2、2，此时的状态就是00011；VSstudio也给出了便于我们快速编译的方式1<<n，代表将1向左移动n个位数，利用“｜”进行拼接。这种方法不仅省去了去重过程，也便于二进制的来回转换。想到这里，思路是否就豁然开朗了呢？

三 代码实现

接下来便利用C++代码对其进行实现，我会对每一步进行详细注释。

以上就是我的想法思路。欢迎大家指正。码字不易，喜欢或有帮助的话大家可以点点赞点点关注。