算法设计与分析（数字塔问题

目录

• 题目——动态规划求解数字塔问题

• 问题描述
• 代码实现
• 输出结果
• 注意事项

• 小结：

题目——动态规划求解数字塔问题

在这篇博客中，我们将探讨一个经典的动态规划问题：在一个金字塔形状的数字矩阵中，如何找到从顶部到底部的最大路径和。每次只能向下移动到相邻的数字，最终我们需要计算出这一最大路径和，并输出该路径。

问题描述

给定一个金字塔形状的整数矩阵，其中每个位置的数字代表路径上的点。我们的目标是从顶端开始，找到一条路径，直到达到底部，使得路径上所有数字的总和最大。在移动时，我们只能向下走到下一行的相邻数字。例如，从位置 (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 开始的索引。

动态规划状态转移：在计算状态转移时，要确保每一步都按照最大值进行更新，以确保路径和的准确性。

路径回溯：回溯时的条件判断要准确，确保能够找到正确的路径。通过判断当前值是否等于来自下方的值，决定路径的选择。