Give me your money!!1
「编写一个函数来计算可以凑成总金额」，可以得出这是一道背包 DP。
「每种硬币的数量是无限的」，进一步得出这是道完全背包。（题型：完全背包）
「最少的硬币个数」，证明这要在背包的前提下，求出最小组成数量。
「多组测试数据」，谨记多组输入 （论 Wrong Answer 与没有多组输入）。（注意：多组输入）
第一步，思考 dp 状态：
\(dp_{i,j}\)：前 \(i\) 种硬币凑出面值 \(j\) 的最少币数。
对于当前一种硬币 \(coins_{i}\) 而言，只有取或不取两种状态。
若取，取后的币数为前 \(i - 1\) 种硬币凑出面值 \(j-w_{i}\times k\) 的总币数加上当前种类所需币数 \(k\)。
若不取，则说明前 \(i - 1\) 种硬币已经能够凑出面值 \(j\)，不需要再取。
第二步，思考状态转移方程：
原本完全背包的状态转移方程是：
但这里我们并不是求总金额以内最大能凑出的面值，而是求凑成总金额的最少币数，于是就有：
通过观察发现，上述方程可以降维。由于对 \(dp_{i}\) 有影响的只有 \(i - 1\)，故可以把前一维抹掉，但需要保证 \(dp_{i,j}\) 可以被 \(dp_{i, j - a_{i}}\) 影响（即 \(dp_{i,j}\) 被计算时 \(dp_{i, j - a_{i}}\) 已经被算出），这才相当于物品 \(i\) 多次被放入背包，所以枚举当前面值 \(j\) 时要正序。
第三步，打出完全背包的代码，把状态转移方程换一下，于是本题的算法部分就完成啦：
for (int i = 1; i <= n; i++) {
for (int j = a[i]; j <= amount; j++) {
dp[j] = min(dp[j], dp[j - a[i]] + 1);
}
}
通过数据范围可以发现，一种硬币的面额是可以比总金额大的，因此可以预处理浅浅优化一下（虽然没什么大的效果）。
因为找的是最小币数，所以 dp 数组要初始化成极大值，而前 \(0\) 种硬币凑成 面值 \(0\) 只需要 \(0\) 种硬币，由此可得 \(dp_{0} = 0\)。
输出时值得注意的是，「如果没有任何一种硬币组合能组成总金额，输出 \(-1\)」；在代码中，这意味着「如果 \(dp_{amount}\) 没有被更新，则输出 \(-1\)」，所以只需要输出时特判一下 \(dp_{amount}\) 若仍是初始值就输出 \(-1\)。
\
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5, A = 1e4 + 5, INF = 0x3f3f3f3f;
int n, amount, a[N], dp[A];
/*
dp(i, j): 前 i 个硬币凑出 j 的最少硬币个数
dp(i, j) = min(dp(i - 1, j - a[i]), dp(i - 1, j));
取这个硬币 or 不取这个硬币
*/
int main() {
freopen("exchange.in", "r", stdin);
freopen("exchange.out", "w", stdout);
while (~scanf("%d %d", &n, &amount)) {
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = a[i]; j <= amount; j++) {
dp[j] = min(dp[j - a[i]] + 1, dp[j]);
}
}
printf("%d\n", dp[amount] == INF ? -1 : dp[amount]); // 可以使用三目运算符来特判
}
return 0;
}
快去 AC 『零钱兑换』 叭~ ヾ(≧▽≦*)o
Bye bye! ??
这是一道简单题题目来自：https://leetcode.cn/problems/two-sum/题目给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。提示：22nums.length104−109−109nums[i]109−109−109target109只会存在一个有效答案进阶：你可以想出一个时间复杂度小于O(n2)O(n^2)O(n2)的算法吗？示例1：输入：nums=[2,7,11,15],targe
518.零钱兑换II1.代码classSolution{public:intchange(intamount,vector&coins){vectorf(amount+1,0);f[0]=1;for(inti=0;i2.动规五部曲1.确定dp数组和其下标含义由题目说可知求选择钱票得到总和为target的方案数，dp[j]相当于选择物品体积相加为i的方案数2.递推公式每次加入物品，都有可能到达体积j,所以在每次加上这个物品到达j时加上这个方案数f[j]+=f[j-coins[i]];3.初始化因为在for循环和dp公式中没有确切的值，肯定需要初始化，初始化第一个就可以保证后面的推导出来了，f[0
没有测评，不知道对不对，仅仅过样例而已试题A:日期统计本题总分：5分【问题描述】小蓝现在有一个长度为100的数组，数组中的每个元素的值都在0到9的范围之内。数组中的元素从左至右如下所示：5686916124919823647759503875815861830379270588570991944686338516346707827689565614010094809128502533现在他想要从这个数组中寻找一些满足以下条件的子序列： 1.子序列的长度为8； 2.这个子序列可以按照下标顺序组成一个yyyymmdd格式的日期，并且要求这个日期是2023年中的某一天的日期，例如202309
2023蓝桥C/C++B组省赛文章目录2023蓝桥C/C++B组省赛试题A:日期统计题目描述枚举参考代码试题B:01串的熵题目描述枚举|模拟参考代码试题C:冶炼金属题意描述取交集参考代码试题D:飞机降落题意描述DFS+剪枝，懒得写试题E:接龙数列题意描述DP参考代码试题F:岛屿个数题意描述dfs|连通块参考代码试题G:子串简写题意描述前缀和参考代码试题H:整数删除题意描述双向链表|最小堆参考代码试题I:景区导游题意描述带权LCA参考代码试题J:砍树题意描述树上差分参考代码试题A:日期统计题目描述【问题描述】小蓝现在有一个长度为100的数组，数组中的每个元素的值都在0到9的范围之内。数组中的元素
83.删除排序链表中的重复元素题目描述给定一个已排序的链表的头head，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。输入：head=[1,1,2]输出：[1,2]解题思路：用一个指向节点类型的指针保存头结点，用另一个指向节点类型的指针对该链表进行遍历，由于是有序的，当出现不同的值就说明不会再出现跟前面的值相同的节点了，最后循环结束的条件是遍历到最后一个节点的时候，也就是该节点的next指向空的时候，停止循环，返回该保存的头结点，另外，如果传过来的头结点是空，则直接返回空。参考代码：/***Definitionforsingly-linkedlist.*structListNod
P1776宝物筛选宝物筛选题目描述终于，破解了千年的难题。小FF找到了王室的宝物室，里面堆满了无数价值连城的宝物。这下小FF可发财了，嘎嘎。但是这里的宝物实在是太多了，小FF的采集车似乎装不下那么多宝物。看来小FF只能含泪舍弃其中的一部分宝物了。小FF对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小FF有一个最大载重为WWW的采集车，洞穴里总共有nnn种宝物，每种宝物的价值为viv_ivi，重量为wiw_iwi，每种宝物有mim_imi件。小FF希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。输入
写在前面以下代码，目前均可通过民间OJ数据（dotcpp&NewOnlineJudge），两个OJ题目互补，能构成全集，可以到对应链接下搜题提交（感谢OJ对题目的支持）如果发现任何问题，包含但不限于算法思路出错、OJ数据弱算法实际超时、存在没考虑到的边界情况等，请及时联系作者题解A.幸运数（模拟）题面题解 由于是填空题，按题意本地暴力，几秒就跑出来结果了，直接交结果代码#includeusingnamespacestd;intans;intmain(){ /* for(inti=1;iB.有奖问答（搜索/dp）题面题解1.搜索：2的30次方种可能，每次要么+10要么清零，遇到100分时
最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南）华为od机试，独家整理已参加机试人员的实战技巧文章目录最近更新的博客使用说明箱子之形摆放题目输入输出示例一输入输出说明备注Code
华为机试一共三道题，分值分别是100，100，200，满分400分，限时2.5小时。我抽到的这三题相对来说比较简单，满分通过，这里做个总结：第一题：数据分类■ 题目描述 对一个数据a进行分类，分类方法为：此数据a（四个字节大小）的四个字节相加对一个给定的值b取模，如果得到的结果小于一个给定的值c，则数据a为有效类型，其类型为取模的值；如果得到的结果大于或者等于c，则数据a为无效类型。比如一个数据a=0x01010101，b=3，按照分类方法计算（0x01+0x01+0x01+0x01）%3=1，所以如果c=2，则此a为有效类型，其类型为1，如果c=1，则此a为无效类型；又如一个数据a=0x01
只做出来(ACDFGH)，挑几个出来，答案不一定正确，但自己测试通过了A、求和求1~20230408的和publicclassMain{ publicstaticvoidmain(String[]args){System.out.println((long)20230409*10115204); }}这里就直接套等差数列的求和公式，答案:204634714038436 D、平均【问题描述】 有一个长度为n的数组(n是10的倍数)，每个数Ai都是区间[0,9]中的整数，小明发现数组里每种数出现的次数不太平均，而更改第i个数的代价为bi，他想更改着若干个数的值使得这10种数出现的次数