下降路径最小和:从第一行下降到最后一行最小路径合为多少?
- 定义
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]
);