Answer: Nvidia OA Question 2024 May | Dynamic Programming | on-campus

Solution: Coin Change — Bottom-Up Dynamic Programming Approach We use Bottom-Up Dynamic Programming. We build a 1D DP table where dp[i] represents the minimum number of coins required to make amount i. Initialize dp[0] = 0 (zero coins needed for amount 0) and all other values to amount + 1 (representing infinity). For each amount from 1 to amount, try every coin. If the coin value is <= current amount, update dp[i] = min(dp[i], dp[i - coin] + 1). If ...