【题目描述】
AcWing 1015. 摘花生

【思路】
DFS
TLE 只通过了两个数据

import java.io.*;
class Main{
    static int N = 110;
    static int q[][] = new int[ N ][ N ];
    static int R, C;
    static int dir[][]  = { {0, 1}, {1, 0}};
    static boolean st[][] = new boolean[N][N];
    static int ans = Integer.MIN_VALUE;
    public static void dfs(int x, int y, int res ){

        if( x == R && y == C ){
            if( res > ans) ans = res;
            return;
        }        
        for(int i = 0; i < 2; i ++)
        {
            int a = x + dir[i][0], b = y + dir[i][1];
            if( a >=1 && a <= R && b >= 1 && b <= C)
            {
                st[a][b] = true;
                dfs(a, b, res + q[a][b]);
                st[a][b] = false;
            }
        }
    }
    public static void main(String args[]) throws Exception{
        BufferedReader bf= new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(bf.readLine());
        while(T-- > 0){
            String str[] = bf.readLine().split(" ");
            R = Integer.parseInt(str[0]);
            C = Integer.parseInt(str[1]);

            for(int i = 1; i <= R; i++){
                String s[] = bf.readLine().split(" ");
                for(int j = 1; j <= C; j++) q[i][j] = Integer.parseInt(s[ j -1 ]);
            }
            ans = 0;
            st[1][1] = true;
            dfs(1, 1, q[1][1]);
            System.out.println(ans);
            }
        bf.close();
    }
}

【思路】
动态规划
当前格子是从左边来的也可能是上边来的，不论是哪种决策。要想从西北角开始，都选择上一步决策所带来的的较大花生数者。

import java.io.*;
class Main{
    static int M = 110, N = 110;

    public static void main(String args[]) throws Exception{
        BufferedReader bf= new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(bf.readLine());
        while(T-- > 0){
            String str[] = bf.readLine().split(" ");
            int R = Integer.parseInt(str[0]), C = Integer.parseInt(str[1]);
            int q[][] = new int[ M ][ N ];
            for(int i = 1; i <= R; i++){
                String s[] = bf.readLine().split(" ");
                for(int j = 1; j <= C; j++) q[i][j] = Integer.parseInt(s[ j -1 ]);
            }
            int f[][] = new int[ M ][ N];
            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]) + q[i][j];
            log.write(f[R][C]+"");
            log.write("\n");
        }
        log.flush();
        log.close();
        bf.close();
    }
}

[HTML_REMOVED]
如果是从后向前状态转移方程式：for(int i = r; i >= 1; i–) for(int j = c; j >= 1; j–) f[i][j] = max(f[i+1][j], f[i][j+1])+a[i][j];，即从下往上，从右往左更新，输出f[1][1]
而不是：for(int i = r; i >= 1; i–) for(int j = c; j >= 1; j–) f[i][j] = max(f[i-1][j], f[i][j-1])+q[i][j];
[HTML_REMOVED]