思路
一个比较简单的 dp 题目。
我们先来设计状态，这一题的 dp 状态设计很简单： dp[i] 的意思是我们使用 i 个Q币最多可以获得多少种展示的方案。对于这种状态下的设计我们可以得到以下的思路。
注意到题面中的 n 很小但是 m 很大，我们可以暴力枚举Q币的数量，最外层循坏 i 从 1 到 n, sum 是买下所有英雄皮肤的Q币数量总和，由于每个英雄的每种皮肤的价格相同，那么我们可以 for(i: 1-n) sum += a[i] * c[i] 来计算价格的总和。第二层循环我们从 sum 到 0 用于枚举当我同 j 个Q币的时候我最多可以得到多少中展示的方案，最后一层循环枚举 k 从 0 到 a[i] 枚举给每个英雄买皮肤。
写完三层循环的时候，我们先来考虑转移的边界，其实这里很简单，只要你的Q币足够我们就可以进行一次转移。if(k * c[i] <= j)
最后我们考虑状态转移方程这是每一道 dp 的关键。这里其实和01背包很像了，但是由于乘法原理的原因，加法运算变成了乘法运算，我们至于要一个01背包的模板并且把加法改成乘法就可以了：
dp[j] = max(dp[j], dp[j - k * c[i]] * k);
感谢观看。