题目描述

blablabla

样例

blablabla

算法1

(暴力枚举)

递归解法，时间复杂度较高，

时间复杂度

参考文献

java代码

class Solution {
    public int getMaxValue(int[][] grid) {
        /*状态表示f[i,j];在这个格子里时，获得的总价格
        状态表示函数里是包含之前信息的，包含有之前的选择信息.
        状态转移f[i,j]=max(f[i,j-1],f[i-1,j])+grid[i][j];i,j要在格子里
        边界条件f[0,j]=f[i,0]=0;
        */
        int n = grid.length-1;//格子的行
        int m = grid[0].length-1;//格子的列
         return f(n,m,grid);
    }
    public int f(int n,int m,int[][] grid){
        if(n<0||m<0) return 0;
        int up =f(n-1,m,grid)+grid[n][m];//要直接返回f(n-1,m)，因为实际上要在递归的式子上计算出上一个f的值
        int left = f(n,m-1,grid)+grid[n][m];
        return up>left?up:left;

    }
}

算法2

循环

正常思路

时间复杂度

O(N^2)

参考文献

java 代码

class Solution {
    public int getMaxValue(int[][] grid) {
        int n =grid.length;//矩阵的行
        int m =grid[0].length;//矩阵的列
        int f[][] = new int[n+1][m+1];//每个走到每个格子中后的最大价值
        for(int i=1;i<n+1;i++)
        {
            for(int j=1;j<m+1;j++)
            {
                f[i][j]=(f[i-1][j]>f[i][j-1]?f[i-1][j]:f[i][j-1])+grid[i-1][j-1];
            }
        }
        return f[n][m];
    }
}