Knapsack : Coin Change
Minimum number of coins of denomination d[n] to add up S (d[0] = 1) O(Sn) 1) dp[s] - min number of coins to add up s 2) dp[s] = 1 + min(dp[s - d[i]] for i in range(n)) 3) dp[S] - min number of coins to add up S Number of ways to add up S with coins of denomination d[n] (d[0] = 1) O(Sn) 1) dp[s] - number of ways to add up s 2) dp[0] = 1 3) dp[s] = SUM(dp[s - d[i]] for i in range(n)) 4) dp[S] = number of ways to add up S
|
Number of coins
// -----------------------------------------------------------------------------
// Coin Change C++
// -----------------------------------------------------------------------------
int coinChange(std::vector<int> &d, int S)
{
int n = d.size();
std::vector<int> dp(S + 1);
for (int s = 1; s <= S; s++) {
int t = S + 1;
int j = 0;
while (j < n && d[j] <= s) {
t = std::min(dp[s - d[j]], t);
j++;
}
dp[s] = t + 1;
}
return dp[S];
}
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
// Coin Change C#
// -----------------------------------------------------------------------------
static int coinChange(int[] d, int S)
{
int n = d.Length;
int[] dp = new int[S + 1];
for (int s = 1; s <= S; s++) {
int t = int.MaxValue;
int j = 0;
while (j < n && d[j] <= s) {
t = Math.Min(dp[s - d[j]], t);
j++;
}
dp[s] = t + 1;
}
return dp[S];
}
// -----------------------------------------------------------------------------
# ------------------------------------------------------------------------------
# Coin Change Python
# ------------------------------------------------------------------------------
def coinChange(d, S):
n = len(d)
dp = [0 for i in range(S + 1)]
for s in range(1, S + 1):
t = S + 1
j = 0
while j < n and d[j] <= s:
t = min(dp[s - d[j]], t)
j += 1
dp[s] = t + 1
return dp[S]
# ------------------------------------------------------------------------------
Number of ways
// -----------------------------------------------------------------------------
// Coin Change C++
// -----------------------------------------------------------------------------
int coinChange(std::vector<int> &d, int S)
{
int n = d.size();
std::vector<int> dp(S + 1);
dp[0] = 1;
for (int i = 0; i < n; i++)
for (int j = d[i]; j <= S; j++)
dp[j] += dp[j - d[i]];
return dp[S];
}
// -----------------------------------------------------------------------------
// -----------------------------------------------------------------------------
// Coin Change C#
// -----------------------------------------------------------------------------
static int coinChange(int[] d, int S)
{
int n = d.Length;
int[] dp = new int[S + 1];
dp[0] = 1;
for (int i = 0; i < n; i++)
for (int j = d[i]; j <= S; j++)
dp[j] += dp[j - d[i]];
return dp[S];
}
// -----------------------------------------------------------------------------
# ------------------------------------------------------------------------------
# Coin Change Python
# ------------------------------------------------------------------------------
def coinChange(d, S):
n = len(d)
dp = [0 for i in range(S + 1)]
dp[0] = 1
for i in range(n):
for j in range(d[i], S + 1):
dp[j] += dp[j - d[i]]
return dp[S]
# ------------------------------------------------------------------------------