Coin Change DP

Coin Change DP

  August 09, 2017    

---

Explanation:

We can make 1 combination for 0 money
Start a loop from 0 to length of array 
Inner Loop from value at i to n
Add value of t[i]+t[i-c[k]] to t[i].


Here in code i have typecasted long to int as we can't give long value to [].

Code:

static long getWays(long n, long[] c){
        int len=(int)n+1;
        long j;
        long t[]=new long[len];
        Arrays.fill(t,0);
        t[0]=1;
        
        for(long i=0;i<c.length;i++)
        {
            for(j=c[(int)i];j<=n;j++)
                t[(int)j]+=t[(int)(j-c[(int)i])];
        }
        
      //  System.out.println("ds");
        return t[(int)n];
    }