C++ 解法, 执行用时: 2ms, 内存消耗: 404KB, 提交时间: 2022-07-15

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        // write code here
        int dp[6][6]={0};
        dp[0][0]=board[0][0];
        for(int i=1;i<6;i++)
        {
            dp[i][0]=dp[i-1][0]+board[i][0];
        }
        for(int j=1;j<6;j++)
        {
            dp[0][j]=dp[0][j-1]+board[0][j];
        }
        for(int i=1;i<6;i++)
        {
            for(int j=1;j<6;j++)
            {
                dp[i][j]=max(dp[i-1][j]+board[i][j],dp[i][j-1]+board[i][j]);
            }
        }
        return dp[5][5];
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 408KB, 提交时间: 2022-01-24

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        // write code here
        int a[7][7]={0};
        for(int i=1;i<7;i++)
            for(int j=1;j<7;j++)
                a[i][j] = board[i-1][j-1] + max(a[i-1][j],a[i][j-1]);
        return a[6][6];
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 412KB, 提交时间: 2021-12-09

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        // write code here
        for(int i=0; i<6; i++){
            for(int j=0; j<6; j++){
                if(i==0 && j==0){
                    continue;
                }
                else if(i==0){
                    board[i][j] += board[i][j-1];
                }
                else if(j==0){
                    board[i][j] += board[i-1][j];
                }
                else{
                    board[i][j] += max(board[i][j-1], board[i-1][j]);
                }
            }
        }
        return board[5][5];
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 412KB, 提交时间: 2021-08-16

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        // write code here
        int x = board.size();
        int y = board[0].size();
        vector<vector<int>> dp(x, vector<int>(y, 0));
        dp[0][0] = board[0][0];
        for(int i=1; i<x; i++) {
            dp[i][0] = dp[i-1][0] + board[i][0];
        }
        for(int j=1; j<y; j++) {
            dp[0][j] = dp[0][j-1] + board[0][j];
        }
        
        for(int i=1; i<x; i++) {
            for(int j=1; j<y; j++) {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + board[i][j];
            }
        }
        return dp[x-1][y-1];
    }
    
};

C++ 解法, 执行用时: 2ms, 内存消耗: 416KB, 提交时间: 2021-08-27

class Bonus {
public:
    int getMost(vector<vector<int> > board) {
        // write code here
        vector<vector<int> > visited(6, vector<int>(6, 0));
        bfs(0, 0, board[0][0], board, visited);
        return res;
    }
    
    void bfs(int x, int y, long value, vector<vector<int> >& board, vector<vector<int> >& visited) {
        if (x ==5 && y == 5) {
            res = max(res, value);
            return ;
        }
        for (int i = 0; i < 2; ++i) {
            int xx = x + dir[i][0];
            int  yy = y + dir[i][1];
            if (visited[xx][yy] || xx >= 6 || yy >= 6) continue;
            visited[xx][yy] = 1;
            bfs(xx, yy, value + board[xx][yy], board, visited);
            visited[xx][yy] = 0;
        }
    }
private:
    struct node{
        int x;
        int y;
        long value;
        node(): x(), y(), value(){}
        node(int x_, int y_, long v): x(x_), y(y_), value(v){}
    };
    int dir[2][2] = {{0,1}, {1,0}};
    long res = 0;
};