下降路径最小和:从第一行下降到最后一行最小路径合为多少?
- 定义
dp[i,j]: 下降到[i,j]这个位置的最小路径和
所以状态转移方程是:
dp[i][j] =
matrix[i][j] +
Math.min(
dp[i - 1][j - 1],
dp[i - 1][j],
dp[i - 1][j + 1]
);
dp[i,j] : 下降到 [i,j] 这个位置的最小路径和

所以状态转移方程是:
dp[i][j] =
matrix[i][j] +
Math.min(
dp[i - 1][j - 1],
dp[i - 1][j],
dp[i - 1][j + 1]
);