算法分析

时间复杂度 $O(n^2)$

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 110;
    static int[][] f = new int[N][N];
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        while(n -- > 0)
        {
            String[] s1 = reader.readLine().split(" ");
            int r = Integer.parseInt(s1[0]);
            int c = Integer.parseInt(s1[1]);
            for(int i = 1;i <= r;i++)
            {
                String[] s2 = reader.readLine().split(" ");
                for(int j = 1;j <= c;j++)
                {
                    f[i][j] = Integer.parseInt(s2[j - 1]);
                }
            }
            for(int i = 1;i <= r;i++)
            {
                for(int j = 1;j <= c;j++)
                {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]) + f[i][j];
                }
            }
            System.out.println(f[r][c]);
        }
    }
}