c++algorithmdynamic-programming

Number of paths using k coins

Given a matrix where every cell has some number of coins. Count number of ways to reach bottom right from top left with exactly k coins. We can move to (i+1, j) and (i, j+1) from a cell (i, j).

Example:

Input: k = 12

   mat[][] = { {1, 2, 3},
               {4, 6, 5},
               {3, 2, 1}
             };

Output: 2 There are two paths with 12 coins

1 -> 2 -> 6 -> 2 -> 1
1 -> 2 -> 3 -> 5 -> 1

I created a recursive definition for this:

Let Count(i, j, k) be the number of ways to get from M[0][0] to M[i][j] using k coins.

Count(i, j, k) = {
   0:                                       if M[i][j] > k,
   Count(i-1, j, k-1) + Count(i, j-1, k-1): if M[i][j] < k
}

My reasoning for this definition is if the entry in the matrix (the number of coins) is greater than the number of coins we want (k), then we can't take that path, so the value in the table should be 0.

If the entry is less than or equal to the number of coins, then we can take that path by adding the number of paths from the top (i-1,j) and left (i, j-1). I subtract k by 1 because the number of coins from the last entry was 1 less.

This is how I do it in the following dynamic programming function:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX_SIZE  10
#define MAX_COINS 20

int Count[MAX_SIZE][MAX_SIZE][MAX_COINS]; // number of ways to get from M[0][0] to M[i][j] using k coins
std::vector<std::vector<int>> M;

int NumOfPaths(int C) {
    size_t N = M.size();
    // Number of paths to (0,0) with 1 coin is 1
    Count[0][0][1] = 1;
    // zero coins doesn't work
    for (size_t i = 0; i < N; ++i) for (size_t j = 0; j < N; ++j)
        Count[i][j][0] = 0;

    // If the number of coins is greater than the max then Count[i][j][k] = 0;
    // Otherwise Count[i][j][k] = Count[i-1][j][k-1]+Count[i][j-1][k-1]

    for (size_t i = 1; i <= N; ++i) {
        for (size_t j = 1; j <= N; ++j) {
            for (int k = 1; k <= C; ++k) {
                if (M[i-1][j-1] >  k) Count[i][j][k] = 0;
                if (M[i-1][j-1] <= k) Count[i][j][k] = Count[i-1][j][k-1] + Count[i][j-1][k-1];
            }
        }
    }
    return Count[N][N][C];
}

int main() {
    M = { {1, 2, 3},
          {4, 6, 5},
          {3, 2, 1}
        };

    cout << NumOfPaths(12);
}

When I apply the function to the example given in the problem statement, it returns 0, which is incorrect.

I'd like to know where my reasoning went wrong and how I can fix it.

Solution

  • Your problems are

    Here's a fixed loop:

    for (size_t i = 0; i < N; ++i) {
  for (size_t j = 0; j < N; ++j) {
    if ((i == 0) && (j == 0)) {
      // Skip 0,0: we've populated that already
      continue;
    }
    for (int k = 1; k <= C; ++k) {
      if (M[i][j] >  k) Count[i][j][k] = 0;
      if (M[i][j] <= k) {
        int ways = 0;
        if (i >= 1) ways += Count[i - 1][j][k - M[i][j]];
        if (j >= 1) ways += Count[i][j - 1][k - M[i][j]];
        Count[i][j][k] = ways;
      }
    }
  }
}
return Count[N-1][N-1][C];

    Alternatively, maybe I misunderstood: were you deliberately counting the top-left square as 1,1 so that you didn't need to check if we were in-bounds for you i-1 and j-1 check, since there'd always be a row of zeroes to spill into? That would make sense for the return [N][N] and the M[i-1][j-1] I suppose. In that case you'd want to