package leetcode.dp;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by Joshua on 7/5/17.
 */
public class CoinChange2 {
    static long getWays(long n, long[] c){
        long[][] dp = new long[(int)n+1][c.length+1];
        dp[0][0] = 1L;
        for (int i=1; i<dp.length; i++) {
            Arrays.fill(dp[i], 0L);
        }

        for (int i=0; i<(int)n; i++) {
            dp[i][1] = 1L;
            for (int j=0; j<c.length; j++) {
                if ((long)i+1L >= c[j]) {
                    dp[i+1][j+1] = dp[i+1][j] + dp[i+1-(int)c[j]][j+1];
                }
                else {
                    dp[i+1][j+1] = dp[i+1][j];
                }
            }
        }
        return dp[(int)n][c.length];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        long[] c = new long[m];
        for(int c_i=0; c_i < m; c_i++){
            c[c_i] = in.nextLong();
        }
        // Print the number of ways of making change for 'n' units using coins having the values given by 'c'
        long ways = getWays(n, c);
        System.out.println(ways);
    }
}

@@ -235,30 +235,8 @@
 1%5D;%0A
-        dp%5B0%5D%5B0%5D = 1L;
 %0A   
@@ -251,17 +251,17 @@
  (int i=
-1
+0
 ; i%3Cdp.l
@@ -310,16 +310,42 @@
 %5D, 0L);%0A
+            dp%5Bi%5D%5B1%5D = 1;%0A
         
@@ -371,22 +371,28 @@
  i=0; i%3C
-(int)n
+dp%5B0%5D.length
 ; i++) %7B
@@ -411,19 +411,91 @@
  dp%5B
-i%5D%5B1%5D = 1L;
+0%5D%5Bi%5D = 1;%0A        %7D%0A        dp%5B0%5D%5B0%5D = 1L;%0A%0A        for (int i=0; i%3C(int)n; i++) %7B
 %0A   

1. need consider both coins is 1 and money is 0 cases