数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++中计算矩阵中达到给定分数的路径数
给定一个包含非负数作为元素的方阵[][]。还给定一个变量分数。目标是通过添加矩阵[][]中的元素来计算达到给定分数的路径数，使得只允许向右移动和向下移动。
从矩阵[0][0]开始，只能移动到矩阵[0][1]（向右移动）或移动到矩阵[1][0]（向下移动），并将值添加到总和=分数中。
让我们通过例子来理解。
例如
输入 - 矩阵[行][列] = { {1, 1}, { 1, 1} } 分数=3
输出 - 达到矩阵中给定分数的路径数为：2
解释 - 分数可以通过以下方式达到
路径 1：添加索引 (0,0) + (0,1) + (1,1) 处的元素 = 1+1+1 = 3
路径 2：添加索引 (0,0) + (1,0) + (1,1) 处的元素 = 1+1+1 = 3
输入 - 矩阵[行][列] = { {1,1,2},{ 2,1,1}, {1,2,2} } 分数=7
输出 - 达到矩阵中给定分数的路径数为：2
解释 - 分数可以通过以下方式达到
路径 1：添加索引 (0,0) + (0,1) + (1,1) + (1,2) + (2,2) 处的元素 = 1+1+1+2+2 = 7
路径 2：添加索引 (0,0) + (0,1) + (1,1) + (2,1) + (2,2) 处的元素 = 1+1+1+2+2 = 7
下面程序中使用的方法如下
在这种方法中，我们将使用动态规划来解决问题。我们将使用两个数组 arr[行][列][大小] 和 check[行][列][大小]。数组 check 将标记矩阵[][] 的单元格，如果它们被访问则为真。数组 arr[][][] 用于存储从矩阵[0][0] 到达特定单元格的路径数。我们将递归地计算路径数。
- 取二维数组 matrix 用于存储数字。
- 取变量 score 作为输入。
- 取两个数组 int arr[行][列][大小] 和 bool check[行][列][大小]。
- 函数 matrix_score(int matrix[行][列], int rows, int cols, int sc) 用于返回达到矩阵中给定分数的路径数。
- 如果分数 sc 小于 0，则返回 0。（结束递归或在输入错误的情况下）
- 如果行数或列数小于 0，则返回 0。（结束递归）。
- 如果第一个单元格等于 sc（输入分数），则返回 1 作为唯一路径。如果不是，则返回 0。
- 如果当前单元格已被访问，则返回此单元格的路径数，作为 arr[行][列][sc]。
- 如果以上所有条件都不成立，则将当前单元格标记为已访问。使用 check[行][列][sc] = true。
- 计算 temp_1 = matrix_score(matrix, rows-1, cols, sc-matrix[rows][cols])
- 计算 temp_2 = matrix_score(matrix, rows, cols-1, sc-matrix[rows][cols])
- 将路径数设置为 arr[行][列][sc] = temp_1 + temp_2。
- 最后返回 arr[行][列][sc]。
例子
#include <iostream>
using namespace std;
#define row 2
#define col 2
#define size 30
int arr[row][col][size];
bool check[row][col][size];
int matrix_score(int matrix[row][col], int rows, int cols, int ways) {
if (ways < 0) {
return 0;
}
if (rows < 0 || cols < 0) {
return 0;
}
if (rows == 0) {
if (cols == 0) {
if (ways == matrix[0][0]) {
return 1;
} else {
return 0;
}
}
}
if (check[rows][cols][ways]) {
return arr[rows][cols][ways];
}
check[rows][cols][ways] = true;
int temp_1 = matrix_score(matrix, rows - 1, cols, ways - matrix[rows][cols]);
int temp_2 = matrix_score(matrix, rows, cols - 1, ways - matrix[rows][cols]);
arr[rows][cols][ways] = temp_1 + temp_2;
return arr[rows][cols][ways];
}
int main() {
int matrix[row][col] = {
{
1,
1
},
{
1,
1
}
};
int ways = 3;
cout << "Count of number of ways to reach a given score in a Matrix are: " << matrix_score(matrix, row - 1, col - 1, ways);
return 0;
}如果我们运行上述代码，它将生成以下输出：
输出
Count of number of ways to reach a given score in a Matrix are: 2
更新于: 2021年1月29日
128 次查看
广告