来自刘汝佳的《算法竞赛入门经典(第二版)》,下面实现代码均为Java 动态规划初步 数字三角形问题(数字塔):有一个非负整数组成的三角形,第一行只有一个数,除了最下行之外的每个数的左下方和右下方各有一个数。如下图所示:计算从顶至底的路径,使得总和最大。 解题思路: 定义状态d(i, j)为从(i, j)出发时能得到的最大和,从(i, j)出发有两种决策,往左或者往右。 要求从(i, j)出发走到底部的最大值d(i, j),则相当于选择从左下走或者从右下走中的较大值,即d(i+1, j)和d(i+1, j+1)的较大值,然后加上a(i, j),可得状态转移方程 d(i, j) = ...