Coin Change (Dynamic Programming)

Hello everyone, just a small tutorial on Coin Change Problem.

Problem:

Given a number of dollars, , and a list of dollar values for distinct coins, , find and print the number of different ways you can make change for dollars if each coin is available in an infinite quantity.

https://www.hackerrank.com/challenges/ctci-coin-change

Solution:

Before coding let’s discuss the problem and solution:

Assume you have unlimited change of { 2, 3, 5, 6}, now you have to tell in how many ways you can make a 10$.

There are many possible ways like, {2,2,2,2,2,} , {2,3,5}.

But how to determine the solution of problem?

There is a recursive solution, in which try all the combinations and if right one is found, increment the count. But doing it recursively is a complex task and the complexity will be O(power(n,m)) and the code is:

package main

import (
       "fmt"
       "sort"
)

var ways int

func coinchange(startIndex int, totalMoney int , coins []int) {
       if startIndex < 0 {
              return
       }
       if totalMoney < 0 {               return        }        if totalMoney == 0 {               ways++               return        }        for i := startIndex;i>=0;i-- {
              coinchange(i,totalMoney-coins[i],coins)
       }

}

func main() {
       var money, numCoins int
       fmt.Scanf("%d%d",&money, &numCoins )
       k := make([]int,numCoins)
       for i:=0;i<numCoins;i++ {
              fmt.Scanf("%d",&k[i] )
       }

       // sort to optimize the calulation
       sort.Ints(k)

       coinchange(numCoins-1,money,k)

       fmt.Println(ways)

}

and this is my output with recursive solution :

Screen Shot 2017-02-18 at 9.15.50 pm.png

The solution is fine and clears few of the test cases, but it gets timeout for the large dataset. The basic problem is while designing our solution we are solving the problems again and again. Like, {6,4} is 10 and {6,2,2}is 10 and {2,2} is 4 and we are recalulating it again and again.

To to solve this we will use Dynamic programming.

package main
import "fmt"

func main() {
       var money, numCoins int
       fmt.Scanf("%d%d",&money, &numCoins )
       k := make([]int,numCoins)
       for i:=0;i<numCoins;i++ {
              fmt.Scanf("%d",&k[i] )
       }
       // make a DP array
       dp := make([]int,money+1)
       dp[0] = 1
       for i:=0;i<numCoins;i++ {
              start := k[i]
              for j:=start;j<=money;j++ {
                     // use the saved solution
                     dp[j] += dp[j-start]
              }
       }
       fmt.Println(dp[money])
}

Screen Shot 2017-02-18 at 9.20.47 pm.png

Our DP Solution clears all the test cases on Hacker  rank.

Explanation:

Now we need a way to save the solution of already solved problems, we will use an array for same.

Screen Shot 2017-02-18 at 9.43.12 pm.png

Map this diagram with code comments and you will figure it out.

Bye everyone, happy coding.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s