若 dp[i][j] 表示从网格 a[i][j] 左上角走到第 i 行第 j 列时能取得的最大数字和,且每次只能向右或向下移动。对于 i > 1 且 j > 1 的位置,正确的状态转移方程是( )。
A:dp[i][j] = a[i][j] + min(dp[i - 1][j], dp[i][j - 1])
B:dp[i][j] = max(dp[i - 1][j - 1], dp[i][j])
C:dp[i][j] = a[i][j] + max(dp[i - 1][j], dp[i][j - 1])
D:dp[i][j] = a[i][j] + dp[i - 1][j - 1]
正确答案:C
答案解析
定义状态 dp[i][j] 表示从网格左上角到达第 i 行第 j 列时所能获得的最大数字和。每次移动只能向右或向下,因此到达 (i, j) 的路径只能来自上方 (i-1, j) 或左方 (i, j-1)。状态转移需考虑这两个方向的最大值。当前格子的值 a[i][j] 必须加入总和。对于 i > 1 且 j > 1 的位置,状态转移由前两个可能位置的最大和决定。初始边界条件由第一行和第一列单独确定,不参与此转移方程构造。
试卷来源:202606 CCF-GESP编程能力等级认证Python七级真题