当前位置: 代码迷 >> 综合 >> LeetCode - Coin Change
  详细解决方案

LeetCode - Coin Change

热度:61   发布时间:2024-01-14 08:41:15.0

题目描述

给你一类货币,货币的张数可以是任意的,然后给你一个aim 目标值,让你找出能兑换出 aim 钱数的最少货币的数量。
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

题目分析

我们先可以按照题目画出一个表,这个表纵轴代表 0 ~ N-1 每种相应的货币,横轴代表从0~aim的钱数。
这里写图片描述
现在如图,我们可以分析,dp[i][j]的结果是由从0 ~ i-1 种货币中,用了0张 arr[i],用了一张 arr[i],用了俩张 arr[i] ,一直到用了k 张 arr[i] 的所有最小组成货币数中的最小值。这个k就是最多有k张 arr[i] 来构成 aim j的最小货币数。
即 dp(i,j) = min { dp[i-1][j]+0, dp[i-1][j-arr[i]]+1 , … , dp[i-1][j-arr[i]*k]+k} k>=0
现在化简这个公式:
??dp[i][j] = min { dp[i-1][j], min{dp[i-1][j-arr[i]]+…+dp[i-1][j-arr[i]*x]+x} x>=1 }
??dp[i][j] = min{ dp[i-1][j], min{dp[i-1][j-arr[i]-arr[i]*0] ,dp[i-1][j-arr[j-arr[i]-arr[i]*y]} y+1>=1}
??min{dp[i-1][j-arr[i]-arr[i]*0] ,dp[i-1][j-arr[i]-arr[i]*y]} y>=0} = dp[i][j-arr[i]]
综上
??dp[i][j] = min { dp[i-1][j] , dp[i][j-arr[i]]+1}
??最终这个公式的字面意思就是,dp[i][j]这个位置是由 0~i-1 个货币组成的最小货币数 和 0~i 种货币 组成 aim-arr[i] 货币的最小货币数 , 这俩个中最小的一种。

初始条件

??初始条件第一列全初始化为0,因为构造0元的最小货币数都是0,第一行可以初始化,只能使用 arr[0] ,构成每一个aim,那么相应的dp值就是 j / arr[0]。

代码

int coinChange(vector<int>& v, int aim)
{vector<vector<int>> res(v.size());for (auto & i : res){i.resize(aim + 1);}int Rows = v.size();int Cols = res[0].size();for (int i = 0; i < Rows; ++i){res[i][0] = 0;}for (int j = 0; j < Cols; ++j){res[0][j] = (j%v[0] == 0) ? j / v[0] : 0x7ffffff;}for (int i = 1; i<Rows; ++i){for (int j = 1; j<Cols; ++j){if ((j - v[i]>=0) && ((res[i][j - v[i]] + 1)<res[i - 1][j])){res[i][j] = res[i][j - v[i]]+1;}else{res[i][j] = res[i - 1][j];}}}if (res[Rows - 1][Cols - 1] == 0x7ffffff)return -1;return res[Rows - 1][Cols - 1];
}
/*****************空间优化版********************/int coinChange(vector<int>& coins, int amount) {int Max = amount + 1;vector<int> dp(amount + 1, Max);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];}

扩展

??不在给你货币的种类的数组,给你一个数组,里面每个下标的值仅能使用一次构成aim 的最小货币数。(有重复的货币)

分析

??实际上这个扩展使这个问题更加的简单化了,dp[i][j] = min { dp[i-1][j],dp[i-1][j-arr[i]]+1 } ,即要么没使用 , 要么使用了1 张。

int coinChange2(vector<int>& v, int aim)
{vector<vector<int>> res(v.size());for (auto & i : res){i.resize(aim + 1);}int Rows = v.size();int Cols = res[0].size();for (int i = 0; i < Rows; ++i){res[i][0] = 0;}for (int j = 0; j < Cols; ++j){if (v[0] / j == 1)res[0][j] = 1;elseres[0][j] = 0x7ffffff;}for (int i = 1; i<Rows; ++i){for (int j = 1; j<Cols; ++j){if ((j - v[i] >= 0) && ((res[i-1][j - v[i]] + 1)<res[i - 1][j])){res[i][j] = res[i-1][j - v[i]] + 1;}else{res[i][j] = res[i - 1][j];}}}if (res[Rows - 1][Cols - 1] == 0x7ffffff)return -1;return res[Rows - 1][Cols - 1];
}
  相关解决方案