矩阵动态规划

import java.util.Scanner;

public class Main {
    // 分析： 从左往右的尝试
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int row = in.nextInt();
        int col  = in.nextInt();
        int[][] array = new int[row][col];
        in.nextLine();
        for (int i = 0; i < row; i++) {
            String[] numbers = in.nextLine().split(" ");
            for (int j = 0; j < col; j++) {
                array[i][j] = Integer.parseInt(numbers[j]);
            }
        }
        System.out.println(process1(array, row, col, 0, 0));
        System.out.println(process2(array));
        System.out.println(process3(array));
    }

    // 暴力递归.   返回值表示从当前位置出发，到结束时，最小的路径.
    private static int process1(int[][] array, int row, int col, int i, int j) {
        if (i == row - 1 && j == col - 1) { // 终止位置
            return array[i][j];
        }
        if (i == row - 1) { // 最后一行，非终止位置
            return array[i][j] + process1(array, row, col, i, j + 1);
        }
        if (j == col - 1) { // 最后一列，非终止位置
            return array[i][j] + process1(array, row, col, i + 1, j);
        }
        // 中间,取朝右或者朝下中较小值，在加上当前值
        return Math.min(process1(array, row, col, i, j + 1), process1(array, row, col, i + 1, j)) + array[i][j];
    }

    // 记忆化搜索，动态规划
    private static int process2(int[][] array) {
        int row = array.length;
        int col = array[0].length;
        int[][] dp = new int[row][col];
        dp[row - 1][col - 1] = array[row - 1][col - 1];
        for (int j = col - 2; j >= 0; j--) {
            dp[row - 1][j] = array[row - 1][j] + dp[row - 1][j + 1];
        }
        for (int i = row - 2; i >= 0; i--) {
            dp[i][col - 1] = array[i][col - 1] + dp[i + 1][col - 1];
        }
        for (int i = row - 2; i >= 0; i--) {
            for (int j = col - 2; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i][j + 1], dp[i + 1][j]) + array[i][j];
            }
        }
        return dp[0][0];
    }

    // 直接修改原数组，从右往左，由下到上推结果. 动态规划
    private static int process3(int[][] array) {
        int row = array.length;
        int col = array[0].length;
        for (int j = col - 2; j >= 0; j--) {
            array[row - 1][j] += array[row - 1][j + 1];
        }
        for (int i = row - 2; i >= 0; i--) {
            array[i][col - 1] += array[i + 1][col - 1];
        }
        for (int i = row - 2; i >= 0; i--) {
            for (int j = col - 2; j >= 0; j--) {
                array[i][j] += Math.min(array[i][j + 1], array[i + 1][j]);
            }
        }
        return array[0][0];
    }
}