10303 数字三角（dp）.zip_4 3 2 1_quietvzi_yourselfy63_算法

#include "pch.h" #include <iostream> #include <algorithm> #include <string.h> using namespace std; int main() { int n; cin >> n; //int arr[n + 1][n + 1]; //int res[n + 1][n + 1];错误 //vs定义二维数组要用以下方法 //联系一维数组理解，int* n1Arr = new int[rows]; int** arr = new int* [n + 1]; for (int i = 0; i < n + 1; i++) { arr[i] = new int[n + 1]; } int** res = new int* [n + 1]; for (int i = 0; i < n + 1; i++) { res[i] = new int[n + 1]; } memset(arr[0], -1, sizeof(int)*(n + 1));//第0行初始化为-1 memset(res[0], -1, sizeof(int)*(n + 1)); for (int i = 1; i <= n; i++) {//数字三角初始化 for (int j = 1; j <= i; j++) { cin >> arr[i][j]; } } // 初始化res结果数组 for (int i = 1; i <= n; i++) { res[n][i] = arr[n][i]; } for (int i = n - 1; i >= 1; i--) { for (int j = 1; j <= i; j++) { // 动规填表 res[i][j] = max(res[i + 1][j], res[i + 1][j + 1]) + arr[i][j]; } } /* // 打印res数组 for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { cout << res[i][j] << " "; } cout << endl; } cout << endl; */ cout << res[1][1] << endl;//最大路径和值 // 找出靠右路径 int y = 1; cout << arr[1][y] << " ";//顶部最大 for (int i = 2; i <= n; i++) { // 从上往下找，只需要比较 y 和 y+1，相应输出 “最大值下标对应的” 原值 if (res[i][y] <= res[i][y + 1]) { cout << arr[i][y + 1] << " "; y = y + 1;//更新y } else { cout << arr[i][y] << " "; } } return 0; } /* 5 7 3 8 8 1 6 2 7 4 4 4 5 2 4 5 30 7 3 8 7 5 假设a[i, j]表示数塔中从上到下第i层，从左向右第j个数的数值， 且设m[i, j]表示数塔从上到下第i层，从左向右第j个数所具有的最大路径和的值。那么就有如下递推的式子： m[i,j]= a[i,j] i=n max{m[i+1,j],m[i+1,j+1]}+a[i,j] 1<=i<n */