题解 | #兑换零钱(一)#
兑换零钱(一)
https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45
2022.0817算法第33题兑换零钱(一)
动态规划问题，这个状态矩阵都没想出来。。。
1、状态矩阵
dp[i]表示目标值为i时的最小零钱兑换种类数。本来想到的是按照零钱数组进行创建状态矩阵
没想出来状态转移方程怎么写。
vector<int> dp(aim+1,aim+1);2、初始值
dp[0]=0;3、状态转移方程
首先对aim进行循环，找到每个目标值的零钱兑换的最小值
针对一个具体的i，循环零钱数组，
找到dp中所有i-arr[j]的位置，其中i>arr[j]
此时只需要找到dp[i-arr[j]]的最小值再+1就行。
就是在之前的最小方案的基础上加上只选择一个硬币的方案。
这个当前值和之前的好多项都是相关联的。不像之前的要么前两项，要么前一项。
for(int i=1;i<=aim;i++){
//循环硬币
for(int j=0;j<arr.size();j++){
//确保硬币不大于当前的目标值
if(arr[j]<=i){
//取之前i-arr[j]方案再加上一个硬币的最小值
dp[i]=min(dp[i],dp[i-arr[j]]+1);
}
}
}
不好想，我觉着挺难的，还需要再悟悟
查看18道真题和解析