题目描述

DP(JAVA实现)

样例

判断思路
f[i][j]，到i,j点的最大花生个数、
到最后一点f[a][b]时，只有两种选择，向右或者向下
因而不断的判断向右和向下的哪个值较大，就可以得到最终结果
个人理解:把问题倒过来，类似与逆递推，目测递推也能实现
import java.util.Scanner;

public class Main {
    static int N=110;
    static int[][] f=new int[N][N];
    static int[][] w=new int[N][N];
    static int max(int a,int b){
        if(a>=b) return a;
        else return b;
    }
    public static void main(String[] args) {
        Scanner s1=new Scanner(System.in);
        int n=s1.nextInt();

        while(n-->0){
            int a=s1.nextInt(),b=s1.nextInt();
        for(int i=1;i<=a;i++){
            for(int j=1;j<=b;j++){
                w[i][j]=s1.nextInt();
            }
        }
        for(int i=1;i<=a;i++)
            for(int j=1;j<=b;j++){
                f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];
            }
    System.out.println(f[a][b]);
           }

    }
}