列出转移方程
求解第 k 行到 bottom 的最短路径时, 需要求此行的任意一个节点 i 加上第 k+1 行到 bottom 的最短路径, 显然这具备了最优子结构的特征;
题目的输入数据结构: input[n][n]
创建缓存: minpath[n], 初始值为最后一层的节点取值因为是自 bottom 到 top, 因此这样赋初始值是合理的, 只有一层的最短路径就是在这些节点中选取
由第 k+1 层的最短路径, 推出第 k 层的最短路径, 标颜色的部分实际上存储着第 k+1 层的最短路径:
minpath[i] = min(minpath[i], minpath[i+1]) + triangle[k][i];
赋完值后, 实际上得到第 k 层的第 i 个节点到 bottom 的最短路径
因此, 遍历第 k 层的所有节点, 便求出了第 k 层的所有节点到 bottom 的最短路径, 实际上就是更新 minpath 数组
来源: https://mp.weixin.qq.com/s?__biz=MzI3NTkyMjA4NA==&mid=2247485183&idx=1&sn=55600d67251a6868d0c4226bf971a2b7&chksm=eb7c2b34dc0ba22229bf470bcff3d963b076cded0673c300ecff91b1a9dad82dd1d722e8d960#rd