Min Coin Change - 动态规划
Min Coin Change - Dynamic Programming
问题 - 给你不同面额的硬币和总金额。编写一个函数来计算您需要最少的硬币数量来弥补 amount.Infinite 硬币供应。
我的方法 - 我遵循了自上而下的方法,但是通过使用 map stl 进行记忆,我得到了 TLE。请帮助找出错误并估计时间复杂度。
这是我的代码 -
// for example coins v = {1,2} and W = 2 then possible solutions are -
// (2) or (1, 1), therefore minimum number of coins required is 1.
// Below is the function calculating the minimum number of coins required for change
int minCoinChange(vector<int> &v, int start, int W, unordered_map<string, int> &lookup){
// v denoting the vector conataining coins with given denomination
// start denoting the start index i.e. 0(initially)
// W denoting the required change
// lookup is map stl for storing values.
// base cases
if(W<0){
return INT_MAX;
}
if(W == 0){
return 0;
}
if(start >= v.size()){
return INT_MAX;
}
// for memoization creating the "key"
string key = to_string(start) + '|' + to_string(W);
// if the key is not found in map then go inside if
if(lookup.find(key) == lookup.end()){
int excl = minCoinChange(v, start+1, W, lookup); // if element is excluded
int incl = 1 + minCoinChange(v, start, W - v[start], lookup); if element is included
lookup[key] = min(incl, excl); // calculating minimum number of coins required and storing in map
}
// if key is already there then return value stored in map
return lookup[key];
}
首先,unordered_map
有一个最坏的 O(n)
查找时间。有一些方法可以优化 unordered_map
性能,例如使用 map.reserve(n)
保留桶的数量,其中 n
是您希望在地图中拥有的唯一项目的数量。
您可以使用 map
而不是最坏情况 O(log(n))
查找时间,但由于该算法的时间复杂度是 O(n * W)
您的 n
和 W
将足够小以适合数组,然后您将使用 O(1)
查找。
下面是对函数的修改,改为使用数组查找:
int minCoinChange(vector<int> &v, int start, int W, vector<vector<int>> &lookup){
// v denoting the vector conataining coins with given denomination
// start denoting the start index i.e. 0(initially)
// W denoting the required change
// lookup is 2d vector for storing already computed values.
// base cases
if (W<0) {
return 1e9;
}
if (W == 0) {
return 0;
}
if (start >= v.size()) {
return 1e9;
}
// if this state wasn't computed before
if (lookup[start][W] == -1) {
int excl = minCoinChange(v, start+1, W, lookup); // if element is excluded
int incl = 1 + minCoinChange(v, start, W - v[start], lookup); // if element is included
lookup[start][W] = min(incl, excl); // calculating minimum number of coins required and storing in map
}
// return the saved value
return lookup[start][W];
}
注:
对于基本情况,不要使用 INT_MAX
,如果添加 1
会溢出,请使用 10^9
.
之类的东西
问题 - 给你不同面额的硬币和总金额。编写一个函数来计算您需要最少的硬币数量来弥补 amount.Infinite 硬币供应。
我的方法 - 我遵循了自上而下的方法,但是通过使用 map stl 进行记忆,我得到了 TLE。请帮助找出错误并估计时间复杂度。
这是我的代码 -
// for example coins v = {1,2} and W = 2 then possible solutions are -
// (2) or (1, 1), therefore minimum number of coins required is 1.
// Below is the function calculating the minimum number of coins required for change
int minCoinChange(vector<int> &v, int start, int W, unordered_map<string, int> &lookup){
// v denoting the vector conataining coins with given denomination
// start denoting the start index i.e. 0(initially)
// W denoting the required change
// lookup is map stl for storing values.
// base cases
if(W<0){
return INT_MAX;
}
if(W == 0){
return 0;
}
if(start >= v.size()){
return INT_MAX;
}
// for memoization creating the "key"
string key = to_string(start) + '|' + to_string(W);
// if the key is not found in map then go inside if
if(lookup.find(key) == lookup.end()){
int excl = minCoinChange(v, start+1, W, lookup); // if element is excluded
int incl = 1 + minCoinChange(v, start, W - v[start], lookup); if element is included
lookup[key] = min(incl, excl); // calculating minimum number of coins required and storing in map
}
// if key is already there then return value stored in map
return lookup[key];
}
首先,unordered_map
有一个最坏的 O(n)
查找时间。有一些方法可以优化 unordered_map
性能,例如使用 map.reserve(n)
保留桶的数量,其中 n
是您希望在地图中拥有的唯一项目的数量。
您可以使用 map
而不是最坏情况 O(log(n))
查找时间,但由于该算法的时间复杂度是 O(n * W)
您的 n
和 W
将足够小以适合数组,然后您将使用 O(1)
查找。
下面是对函数的修改,改为使用数组查找:
int minCoinChange(vector<int> &v, int start, int W, vector<vector<int>> &lookup){
// v denoting the vector conataining coins with given denomination
// start denoting the start index i.e. 0(initially)
// W denoting the required change
// lookup is 2d vector for storing already computed values.
// base cases
if (W<0) {
return 1e9;
}
if (W == 0) {
return 0;
}
if (start >= v.size()) {
return 1e9;
}
// if this state wasn't computed before
if (lookup[start][W] == -1) {
int excl = minCoinChange(v, start+1, W, lookup); // if element is excluded
int incl = 1 + minCoinChange(v, start, W - v[start], lookup); // if element is included
lookup[start][W] = min(incl, excl); // calculating minimum number of coins required and storing in map
}
// return the saved value
return lookup[start][W];
}
注:
对于基本情况,不要使用 INT_MAX
,如果添加 1
会溢出,请使用 10^9
.