动态规划第一题---硬币找零问题

一. 问题描述:假设有几种硬币,如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<

【动态规划第一题---硬币找零问题】

    推荐阅读