题解 | 年终奖_牛客博客

解题思路

这是一个典型的动态规划问题。关键点：

状态定义：
- $dp[i][j]$ 表示从起点到达 $(i,j)$ 位置能获得的最大价值
状态转移：
- $dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + board[i][j]$
- 只能从上方或左方到达当前位置
边界条件：
- 第一行只能从左往右
- 第一列只能从上往下

代码

cpp
java
python

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        int n = 6;
        vector<vector<int>> dp(n, vector<int>(n));
        
        // 初始化第一个格子
        dp[0][0] = board[0][0];
        
        // 初始化第一行
        for(int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + board[0][j];
        }
        
        // 初始化第一列
        for(int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][0] + board[i][0];
        }
        
        // 动态规划填表
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + board[i][j];
            }
        }
        
        return dp[n-1][n-1];
    }
};

import java.util.*;

public class Bonus {
    public int getMost(int[][] board) {
        // write code here
        int n = 6;
        int[][] dp = new int[n][n];
        
        // 初始化第一个格子
        dp[0][0] = board[0][0];
        
        // 初始化第一行
        for(int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j-1] + board[0][j];
        }
        
        // 初始化第一列
        for(int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][0] + board[i][0];
        }
        
        // 动态规划填表
        for(int i = 1; i < n; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + board[i][j];
            }
        }
        
        return dp[n-1][n-1];
    }
}

class Bonus:
    def getMost(self, board):
        # write code here
        n = 6
        dp = [[0 for x in xrange(n)] for x in xrange(n)]
        
        dp[0][0] = board[0][0]
        
        for j in xrange(1, n):
            dp[0][j] = dp[0][j-1] + board[0][j]
        
        for i in xrange(1, n):
            dp[i][0] = dp[i-1][0] + board[i][0]
        
        for i in xrange(1, n):
            for j in xrange(1, n):
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + board[i][j]
        
        return dp[n-1][n-1]

算法及复杂度

算法：动态规划
时间复杂度： $\mathcal{O(n^2)}$ ，需要填充整个 $dp$ 表
空间复杂度： $\mathcal{O(n^2)}$ ，需要 $dp$ 数组存储中间结果