PHP Program for Coin Change using Dynamic Programming (Memoization)
The above recursive solution has Optimal Substructure and Overlapping Subproblems so Dynamic programming (Memoization) can be used to solve the problem. So 2D array can be used to store results of previously solved subproblems.
Step-by-step approach:
- Create a 2D dp array to store the results of previously solved subproblems.
- dp[i][j] will represent the number of distinct ways to make the sum j by using the first i coins.
- During the recursion call, if the same state is called more than once, then we can directly return the answer stored for that state instead of calculating again.
Below is the implementation of the above approach:
PHP
<?phpfunction countWays($coins, $n, $sum, &$dp) { // Base Case if ($sum == 0) { $dp[$n][$sum] = 1; return 1; } // If the subproblem is previously calculated, return the result if ($n <= 0 || $sum < 0) { return 0; } if ($dp[$n][$sum] != -1) { return $dp[$n][$sum]; } // Two options for the current coin $dp[$n][$sum] = countWays($coins, $n, $sum - $coins[$n - 1], $dp) + countWays($coins, $n - 1, $sum, $dp); return $dp[$n][$sum];}$tc = 1;// Read input here if neededwhile ($tc--) { $n = 3; $sum = 5; $coins = [1, 2, 3]; $dp = array_fill(0, $n + 1, array_fill(0, $sum + 1, -1)); $res = countWays($coins, $n, $sum, $dp); echo $res . PHP_EOL;}?> |
5
Time Complexity: O(N*sum), where N is the number of coins and sum is the target sum.
Auxiliary Space: O(N*sum)
PHP Program for Coin Change | DP-7
Write a PHP program for a given integer array of coins[ ] of size N representing different types of denominations and an integer sum, the task is to find the number of ways to make a sum by using different denominations.
Examples:
Input: sum = 4, coins[] = {1,2,3},
Output: 4
Explanation: there are four solutions: {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}.Input: sum = 10, coins[] = {2, 5, 3, 6}
Output: 5
Explanation: There are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}.