数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时装研究
法律研究N x N 网格中的最小下降路径总和，用 C++ 编写
问题陈述
- 给定一个 N x N 的整数矩阵 A。任务是找到下降穿过 A 的最小路径总和。
- 下降路径将从第一行的某个元素开始，在最后一行结束。
- 它从每一行选择一个元素。下一行的选择必须在与上一行相差至多 1 的列中
示例
If N = 2 and matrix is:
{
{5, 10},
{25, 15}
} then output will be 20 as element 5 and 15 are selected示例
#include <bits/stdc++.h>
#define MAX 2
using namespace std;
int getMinSumPath(int matrix[MAX][MAX]) {
for (int row = MAX - 2; row >= 0; --row) {
for (int col = 0; col < MAX; ++col) {
int val = matrix[row + 1][col];
if (col > 0) {
val = min(val, matrix[row +1][col - 1]);
}
if (col + 1 < MAX) {
val = min(val, matrix[row +1][col + 1]);
}
matrix[row][col] = matrix[row][col] +val;
}
}
int result = INT_MAX;
for (int i = 0; i < MAX; ++i)
result = min(result, matrix[0][i]);
return result;
}
int main() {
int matrix[MAX][MAX] = {
{5, 10},
{25, 15},
};
cout << "Minimum sum path = " << getMinSumPath(matrix)
<< endl;
return 0;
}编译并执行以上程序后，将生成如下输出
输出
Minimum sum path = 20
更新于: 2019-12-23
143 次浏览
广告