lets understand coins problem ,Given N and an array(say coins[]) that contains some numbers(coins in rupees). N is a coin, and the array contains various coins. The task is to make the change of N using the coins of the array. Make a change in such a way that a minimum number of coins are used.
#include <bits/stdc++.h> using namespace std; int coins[] = {10, 25, 5}; // coins array int dp[1000] = {0}; // array for memoisation int minCoins(int N, int M) // N is the sum , M is total_coins {
for (int i = 0; i <= N; i++)
dp[i] = INT_MAX; // Initialise all dp[] value to INT_MAX
dp[0] = 0; // Base case if sum becomes zero min rupees = 0
// Iterating in the outer loop for possible values of sum between 1 to N
// Since our final solution for sum = N might depend upon any of these values
for (int i = 1; i <= N; i++)
{
// Inner loop denotes the index of coin array.
// For each value of sum, to obtain the optimal solution.
for (int j = 0; j < M; j++)
{
// i ?> sum
// j ?> next coin index
// If we can include this coin in our solution
if (coins[j] <= i)
{
// Solution might include the newly included coin
dp[i] = min(dp[i], 1 + dp[i - coins[j]]);
}
}
}
return dp[N];
}
int main() {
int sum = 30; // the money to convert
int total_coins = 3; // total availability of coins
cout << "Minimum coins needed are " << minCoins(sum, total_coins);
}