Dynamic programming

Ways of Coin Change

Problem: given a set of n coins of different face values C, and a value V, find number of ways of making change for V.

We start with a substructure dp[i][j] representing #ways using coins [0,i] for value j. 0 means using no coins. i means using coins until C[i-1]. I know this notation is a bit confusing, but I think it's good to explicitly modeling the case of using no coins as an initial setup.

So now we know we want dp[n][V] and we'll approach this value progressively. But how?

Since we start from dp[0][0], we have to increment i and/or j in each computation. Note for dp[i][j], assume we have all previous values for dp[i'][j'](i'<i, j'<j), since the goal is to see what coins are included in the final set, there are two choices for current coin i-1: to include it or not?

• If C[i-1]>j, we can't include it, and dp[i][j] = dp[i-1][j];
• Otherwise, dp[i][j] = dp[i-1][j] + dp[i][j-C[i-1]]

• Otherwise, dp[i][j] = dp[i-1][j] + dp[i-1][j-C[i-1]]

How do we actually implement above algorithm? Where do we start? How to write the loops?

Well if you simulate the computation on paper, you will find you are essentially doing a table-filling. You start from top-left corner, work your way to the right. After finishing the row, you shift down to next row. Apparently the outer loop is on i. And the top row should be all 0s except dp[0][0]=1.

int dp[][] = new int[n+1][target+1];
dp[0][0]=1;

//no way if target > 0 while using 0 candidates
for(int i=1;i<=target;i++) {
  dp[0][i]=0;//this actually populates the top row of dp table
}

for(int i=1;i<=n;i++) {
  for(int j=0;j<=target;j++) {
    //if target is smaller than current candidate value, have to skip current candidate
    if(j<C[i-1]) {
      dp[i][j] = dp[i-1][j];
    }
    //otherwise two choices: using current candidate, or not 
    else {
      dp[i][j] = dp[i][j - C[i-1]]+dp[i-1][j];
    }
  }
}

Notice for above code,