One classic example of a problem that can be solved using both greedy algorithms and dynamic programming is the "coin change" problem.
The problem statement goes as follows: Given a target amount of money and a set of coin denominations, what is the minimum number of coins needed to make up the target amount? For example, if the target amount is 11 and the coin denominations are [1, 5, 10], the answer should be 2 (one 5-cent coin and six 1-cent coins).
One possible solution using the greedy approach is to always pick the largest coin denomination that is less than or equal to the remaining amount. This strategy is known as the "coin denomination sorting" algorithm. While this algorithm can provide a correct solution for many cases, it may fail for certain inputs. For instance, if the coin denominations are [1, 3, 4] and the target amount is 6, the algorithm would return 2 (two 3-cent coins), whereas the optimal solution is 2 (one 4-cent coin and two 1-cent coins).
On the other hand, the problem can also be solved using dynamic programming. One possible approach is to build an array of size (target_amount + 1), where each element represents the minimum number of coins needed to make up the corresponding amount. The base case is when the amount is zero, which requires zero coins. For each amount, we iterate over all possible coin denominations and compute the minimum number of coins required by taking the minimum of (current minimum) and (minimum for the remaining amount plus one coin). The final answer is the value at array[target_amount].
Here’s an implementation of the dynamic programming solution in Java:
public static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}As we can see, the dynamic programming solution guarantees the optimal solution for any set of coin denominations and target amount, while the greedy algorithm may fail for some cases. However, the dynamic programming solution requires more space and time complexity than the greedy algorithm, especially for large inputs or non-uniform coin denominations. Therefore, the choice of solution depends on the trade-off between optimality and efficiency in a given scenario.