算法可视化
入门执行逻辑
数字三角形:最大路径和
从顶层走到底层,每次只能向下或右下,求路径上数字和的最大值。自底向上合并:dp[j] = a[i][j] + max(下一层的两个)。
main.cpp第 1 行
1// 数字三角形: 自底向上, dp[j] = 当前层第 j 个的最大路径和
2for (int i = n-2; i >= 0; i--)
3 for (int j = 0; j <= i; j++)
4 dp[j] = a[i][j] + max(dp[j], dp[j+1]);
5// 答案: dp[0] = 30
变量表1 个变量
底层[4, 5, 2, 6, 5]
数组 a
比较交换已就位
40
51
22
63
54
1/16
三角形共 5 层,从最底层开始。dp 初始为底层:[4, 5, 2, 6, 5]
1 / 16