目录
- 题目——动态规划求解数字塔问题
- 问题描述
- 代码实现
- 输出结果
- 注意事项
- 小结:
题目——动态规划求解数字塔问题
在这篇博客中,我们将探讨一个经典的动态规划问题:在一个金字塔形状的数字矩阵中,如何找到从顶部到底部的最大路径和。每次只能向下移动到相邻的数字,最终我们需要计算出这一最大路径和,并输出该路径。
问题描述
给定一个金字塔形状的整数矩阵,其中每个位置的数字代表路径上的点。我们的目标是从顶端开始,找到一条路径,直到达到底部,使得路径上所有数字的总和最大。在移动时,我们只能向下走到下一行的相邻数字。例如,从位置 (i, j)
只能移动到 (i+1, j)
或 (i+1, j+1)
。
为了求解这个问题,我们可以使用动态规划的方法,通过自下而上的方式逐步计算出每个位置的最大路径和。最后,路径和存储在一个辅助数组中,我们可以通过回溯的方法找出实际的路径。
代码实现
#include <iostream>
#define N 5
using namespace std;
int dtower(int a[][N+1], int s[][N+1], int n){
/*
a:原矩阵
s:最优值
n:矩阵大小
*/
for (int i=1; i<=n; i++) s[n][i] = a[n][i]; // 拷贝最后一行
for (int i=n-1; i>0; i--){ // 递推公式
for (int j=1; j<=i; j++){
s[i][j] = a[i][j] + max(s[i+1][j], s[i+1][j+1]);
}
}
return s[1][1];
}
void TraceBack(int a[][N+1], int s[][N+1], int i, int j, int n){
// 终止条件
if (i == n) cout << i << ", " << j << endl;
// 递归
else{
cout << i << ", " << j << endl;
if (s[i][j] == a[i][j] + s[i+1][j]) TraceBack(a, s, i+1, j, n); // 选择下方
else TraceBack(a, s, i+1, j+1, n); // 选择下右方
}
}
int main() {
// 原矩阵
int a[N+1][N+1] = {
{0, 0, 0, 0, 0, 0},
{0, 7, 0, 0, 0, 0},
{0, 3, 8, 0, 0, 0},
{0, 8, 1, 0, 0, 0},
{0, 2, 7, 4, 4, 0},
{0, 4, 5, 2, 6, 5}};
// 最优值矩阵
int s[N+1][N+1];
// 递推求最优值
cout << dtower(a, s, N) << endl;
// 递归构建最优解
TraceBack(a, s, 1, 1, N);
}
输出结果
注意事项
数组下标:在使用数组时,请注意下标的范围,避免越界错误。这里我们定义了 N+1
的数组,以简化从 1
开始的索引。
动态规划状态转移:在计算状态转移时,要确保每一步都按照最大值进行更新,以确保路径和的准确性。
路径回溯:回溯时的条件判断要准确,确保能够找到正确的路径。通过判断当前值是否等于来自下方的值,决定路径的选择。
标签:数字,int,路径,矩阵,算法,数组,设计,动态 From: https://blog.51cto.com/u_16672541/12110300