# 正好有 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; } ```