---
title : Coin Change
tags : Dynamic Programming
---
###### tags: `Hacker Rank`, `DP`

Coin Change
===

Source
---
https://www.hackerrank.com/challenges/ctci-coin-change/problem?h_r=internal-search

Problem Analytica
---
Given a number of dollars and an array of denominations of coins, determine how many ways you can make change. For example, making change for $12$ dollars from coin denominations $coins = [1,2,5,10]$, there are $15$ ways to make change:

Point of Attack
---
When problem comes to having difference options, there is a typical thinking in **This or That**.
> Should we select `pick` **This** or `not`.

What is the way to eliminate overlapped subproblem?
:::spoiler
- Dynamic Programming
- Memorization

:::

Algorithm
---

start
if (have money left) then (yes)
    if (pick this coin) then (yes)
    :pick this;
    else
    :pick next one;
    start
    endif
elseif (money is empty) then (yes)
  :that is way to make a change;
  stop
elseif (have a debt) then (yes)
  :that is not a valid way;
    stop
else (nothing)
  :repeat;
endif
stop

## Without optimizing the structure

ways 0 _ = 1
ways n [] = 0
ways n (x:xs) 
    | n < 0 = 0
    | n < x = ways n xs
    |othewise = ways (n-x) (x:xs) + ways n xs

The example :

ways 12 [1,2,5,10]

will generate a overlapped call dependency on the stack.
Let's view the invoked Tree

digraph hierarchy {

                nodesep=1.0 // increases the separation between nodes

                node [color=Green,fontname=Courier,shape=circle] //All nodes will this shape and colour
                edge [color=Blue, style=dashed] //All the lines look like this

                "ways 12 [1,2,5,10]"->{"ways 11 [1,2,5,10]","ways 12 [2,5,10]"}
                "ways 11 [1,2,5,10]"->{"ways 10 [1,2,5,10]","ways 11 [2,5,10]"}
                "ways 12 [2,5,10]"->{"ways 10 [2,5,10]","ways 12 [5,10]"}
                "ways 10 [1,2,5,10]" -> {"ways 9 [1,2,5,10]" ,"ways 10 [2,5,10]" }
                "ways 11 [2,5,10]" -> {"ways 9 [2,5,10]" ,"ways 11 [5,10]" }
                "ways 10 [2,5,10]" ->{"ways 8 [2,5,10]","ways 10 [5,10]"}
                "ways 12 [5,10]" -> {"ways 7 [5,10]","ways 12 [10]" }
                "ways 9 [1,2,5,10]" -> {"ways 8 [1,2,5,10]","ways 9 [2,5,10]"}
                "ways 8 [1,2,5,10]" -> {"ways 7 [1,2,5,10]","ways 8 [2,5,10]"}
}

We can expect the invoked Tree grow exponentially with large parameters.

## Momentization

Hierarcy Decompsition
---

Further Readings
---
###### tags: `Hacker Rank`