# 正好有 k 个硬币的路径数 > 原文： [https://www.geeksforgeeks.org/number-of-paths-with-exactly-k-coins/](https://www.geeksforgeeks.org/number-of-paths-with-exactly-k-coins/) 给定一个矩阵，其中每个单元格都有一定数量的硬币。 用正确的 k 个硬币计算从右上角到右下角的方式数。 我们可以从像元（i，j）移至（i + 1，j）和（i，j + 1）。 **示例**： ``` 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 ``` [](https://practice.geeksforgeeks.org/problem-page.php?pid=383) ## 强烈建议您在继续解决方案之前，单击此处进行练习。 可以递归定义上述问题，如下所示： ``` pathCount(m, n, k): Number of paths to reach mat[m][n] from mat[0][0] with exactly k coins If (m == 0 and n == 0) return 1 if mat[0][0] == k else return 0 Else: pathCount(m, n, k) = pathCount(m-1, n, k - mat[m][n]) + pathCount(m, n-1, k - mat[m][n]) ``` 下面是上述递归算法的实现。 ## C++ ```cpp // A Naive Recursive C++ program  // to count paths with exactly // 'k' coins #include <bits/stdc++.h> #define R 3 #define C 3 using namespace std; // Recursive function to count paths with sum k from // (0, 0) to (m, n) int pathCountRec(int mat[][C], int m, int n, int k) {     // Base cases     if (m < 0 || n < 0) return 0;     if (m==0 && n==0) return (k == mat[m][n]);     // (m, n) can be reached either through (m-1, n) or     // through (m, n-1)     return pathCountRec(mat, m-1, n, k-mat[m][n]) +            pathCountRec(mat, m, n-1, k-mat[m][n]); } // A wrapper over pathCountRec() int pathCount(int mat[][C], int k) {     return pathCountRec(mat, R-1, C-1, k); } // Driver program int main() {     int k = 12;     int mat[R][C] = { {1, 2, 3},                       {4, 6, 5},                       {3, 2, 1}                   };     cout << pathCount(mat, k);     return 0; } ```