使用k个硬币的路径数

Question

给定一个矩阵，其中每个单元格都有一定数量的硬币。计算用
k
枚硬币从左上角到达右下角的方法数。我们可以从单元格
(i+1, j)
移动到
(i, j+1)
和
(i, j)
。

示例：

输入：k = 12
   mat[][] = { {1, 2, 3},
               {4, 6, 5},
               {3, 2, 1}
             };
输出： 2 有两条路有12个金币

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

我为此创建了一个递归定义：

令

Count(i, j, k)

为使用

M[0][0]

硬币从

M[i][j]

到

的方式数量。

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
}

我对这个定义的推理是，如果矩阵中的条目（硬币数量）大于我们想要的硬币数量（

），那么我们就不能走这条路，所以表中的值应该是 0.

如果条目小于或等于硬币数量，那么我们可以通过添加从顶部

(i-1,j)

到左侧

(i, j-1)

的路径数来选择该路径。我将

减 1，因为上次输入的硬币数量少了 1。

这就是我在以下动态规划函数中的做法：

#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);
}

当我将该函数应用于问题陈述中给出的示例时，它返回 0，这是不正确的。

我想知道我的推理哪里出了问题以及如何解决它。

Answer 1

你的问题是

你正在初始化
```
Count[0][0][1] = 1
```
，而它应该是
```
Count[0][0][M[0][0]]
```
（尽管这里是一样的）
您永远不会填写
```
Count[0][j]
```
或
```
Count[i][0]
```
，即，从您循环的任何单元格到 0,0 都没有完整的路径
您的指数上限相差一；你想要
```
< N
```
在循环中并返回 N-1 因为向量是零索引的
您正在循环中针对
```
M[i-1][j-1]
```
测试 k，而不是
```
M[i][j]
```
您减去的是一枚硬币，而不是
```
M[i][j]
```
硬币（正如Edward和vu1p3n0x在评论中指出的那样）

这是一个固定循环：

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];

或者，也许我误解了：你是否故意将左上角的正方形计算为 1,1，这样你就不需要检查我们是否在你的 i-1 和 j-1 检查中，因为有总是会出现一排零？我认为这对于返回 [N][N] 和 M[i-1][j-1] 是有意义的。在这种情况下，你会想要

将 1,1 而不是 0,0 初始化为 [1][1][1] = 1，并在循环中跳过 1,1，如上所述
现在从 k 中减去 M[i-1][j-1] 个硬币，而不是 1
如果您确实需要应对 10x10，请将 MAX_COINS 加一，否则您只能接受 9x9

Answer 2

有没有办法在不使用 3d 数组的情况下解决这个问题？ “导入java.util.Arrays；

公共类 Number_of_paths_in_a_matrix_with_k_coins {

public static long MOD = 1000000007;

public long numberOfPath(int n, int k, int [][]arr) {
    // code here
    long dp[][] = new long[n][n];

    for (long rows[] : dp){
        Arrays.fill(rows,-1);
    }

    return MemoUtil(k,n-1,n-1,arr,dp);
}

public static long MemoUtil(int k, int i, int j,int arr[][], long dp[][]){

    if(i == 0 && j == 0 )  return k == arr[0][0] ? 1 : 0L;

    if (i < 0 || j < 0 || k < 0) return 0;

    if (dp[i][j] != -1) return dp[i][j];

    long left = i > 0 && k > 0 ? MemoUtil(k - arr[i][j], i -1, j, arr,dp) %MOD : 0L;

    long right = j > 0 && k > 0 ? MemoUtil(k- arr[i][j], i, j-1, arr, dp) % MOD : 0L;

    return dp[i][j] =  (left + right) %MOD;

}

} “我尝试过，但这是错误的

使用k个硬币的路径数

问题描述投票：0回答：2

2个回答

最新问题

使用k个硬币的路径数

问题描述 投票：0回答：2

2个回答

最新问题

问题描述投票：0回答：2