PHP Program for Coin Change using Dynamic Programming (Tabulation)
- Create a 2D dp array with rows and columns equal to the number of coin denominations and target sum.
dp[0][0]
will be set to
1
which represents the base case where the target sum is 0, and there is only one way to make the change by not selecting any coin.- Iterate through the rows of the dp array (i from 1 to
n
), representing the current coin being considered.
- The inner loop iterates over the target sums (
j
from 0 tosum
).
- Add the number of ways to make change without using the current coin, i.e.,
dp[i][j] += dp[i-1][j]
.- Add the number of ways to make change using the current coin, i.e.,
dp[i][j] += dp[i][j-coins[i-1]]
.dp[n][sum]
will contain the total number of ways to make change for the given target sum using the available coin denominations.
Below is the implementation of the above approach:
PHP
<?php function countDistinctWays( $coins , $n , $sum ) { $dp = array_fill (0, $sum + 1, 0); $dp [0] = 1; for ( $i = 0; $i < $n ; $i ++) { for ( $j = $coins [ $i ]; $j <= $sum ; $j ++) { $dp [ $j ] += $dp [ $j - $coins [ $i ]]; } } return $dp [ $sum ]; } $coins = [2, 5, 3, 6]; $n = 4; $sum = 10; echo countDistinctWays( $coins , $n , $sum ) . PHP_EOL; ?> |
5
Time complexity : O(N*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}.