本题是线性dp，一般根据最后一步的走法来进行集合划分

        Scanner scanner=new Scanner(System.in);
        int t=scanner.nextInt();
        for(int q=0;q<t;q++) {
            int rr=scanner.nextInt(),cc=scanner.nextInt();
            int[][] g=new int[110][110];
            int[][] f=new int[110][110];//表示所有从起点到（i，j）的合法路线的集合，存储最大值
            for(int i=1;i<=rr;i++) {
                for(int j=1;j<=cc;j++)
                    g[i][j]=scanner.nextInt();
            }
            for(int i=1;i<=rr;i++) {
                for(int j=1;j<=cc;j++) {//最后一步中，有向右走和向下走两种走法
                    f[i][j]=Math.max(f[i-1][j]+g[i][j], f[i][j-1]+g[i][j]);
                }
            }
            System.out.println(f[rr][cc]);
        }