米兔收集胡萝卜

class Solution:
    def maxPathSum(self , a ):
        cols=len(a[0])
        rows=len(a)
        for i in range(1,cols):
            a[0][i]=a[0][i-1]+a[0][i]
        for i in range(1,rows):
            a[i][0]=a[i-1][0]+a[i][0]      
        for i in range(1,rows):
            for j in range(1,cols):
                a[i][j]=max(a[i-1][j], a[i][j-1])+a[i][j]
        return a[rows-1][cols-1]

基础dp，注意使用原数组操作降低空间复杂度。

class Solution:
    def maxPathSum(self , a ):
        for i in range(len(a)):
            for j in range(len(a[0])):
                if i > 0 and j > 0: a[i][j] += max(a[i-1][j],a[i][j-1])
                elif i > 0: a[i][j] += a[i-1][j]
                elif j > 0: a[i][j] += a[i][j-1]
        return a[-1][-1]

import java.util.Random;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String[] s=scanner.nextLine().split(" ");
        int n=Integer.parseInt(s[0]),m=Integer.parseInt(s[1]);
        int[][] a=new int[n][m];
        Random random=new Random(1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j]= random.nextInt(10);
            }
        }
        int[][] dp=new int[n][m];
        dp[0][0]=a[0][0];
        for (int i = 1; i < m; i++) {
            dp[0][i]=dp[0][i-1]+a[0][i];
        }
        for (int i = 1; i < n; i++) {
            dp[i][0]=dp[i-1][0]+a[i][0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+a[i][j];
            }
        }

        System.out.println(dp[n-1][m-1]);

    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector<vector<>> 
     * @return int整型
     */
    int maxPathSum(vector<vector<int> >& a) {
        // write code here
        int n = a.size();
        int m = a[0].size();
        //dp[i][j]表示走到第[i,j]个格子时的最大萝卜数
        vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i-1][j-1];//上面和左边格子取大者
            }
        }
        return dp[n][m];
    }
};