一. 问题描述:假设有几种硬币,如1,3,5并且数量无限,请找出能够组成某个数目的找零,要求所使用的硬币数要最少, 返回需要最少的硬币数目。
二.解题思路:类似这种求极值的问题,首先可以想到的是这个问题是动态规划问题。解决动态规划问题有如下几个步骤:
1. 明确子问题;2.状态表示;3.状态转移方程;4.确定边界;
三.具体思路:具体说来,硬币找零问题的子问题为,需要求解出1-amount 之间每一个找零数需要的最少硬币数,其中amount为找零数;找零问题的状态表示:dp[i]:表示找零数为i时需要的最少硬币数;状态转移方程:dp[i]=min(dp[i],dp[i-coins[j]]+1),其中coins[j]表示第j中硬币面值。确定边界:边界为i=amount。
四.带注释的代码
#include
#include
#include
using namespace std;
class Solution
{
public:
int coinChange(vector&coins,int amount)
{
vector dp(amount + 1, amount + 1);
//初始化:前面参数为容器元素个数,后面参数为容器元素的值
dp[0] = 0;
for (int i = 1;
i <= amount;
++i)
{
for (int j = 0;
j < coins.size();
++j)
{
if (coins[j] <= i)//硬币的面值肯定要小于需要找零的数值
{
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
//状态转移方程
}
}
}
return (dp[amount] > amount) ? -1 : dp[amount];
}
};
int main()
{
Solution solve;
int a[4]={1,3,5,10};
vectorb(a,a+4);
cout<
【动态规划第一题---硬币找零问题】