矩阵动态规划

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine().trim());
        int n = Integer.parseInt(br.readLine().trim());
        int[][] grid = new int[m][n];
        for(int i = 0; i < m; i++){
            String[] row = br.readLine().trim().split(" ");
            for(int j = 0; j < n; j++) grid[i][j] = Integer.parseInt(row[j]);
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0 && j == 0)
                    grid[i][j] = grid[i][j];
                else if(i == 0)
                    grid[i][j] += grid[i][j - 1];     // 上边界只能从左边过来
                else if(j == 0)
                    grid[i][j] += grid[i - 1][j];     // 左边界只能从上边过来
                else      // 选择两种方案中路径小的
                    grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        System.out.println(grid[m - 1][n - 1]);
    }
}

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];
    }
}

m=int(input().strip())
n=int(input().strip())
M=[]
for i in range(m):
    M.append(list(map(int,input().strip().split())))
dp=[[0]*(n) for _ in range(m)]
for i in range(m):
    for j in range(n):
        if i-1>=0:
            up=dp[i-1][j]+M[i][j]
        else:up=dp[i][j-1]+M[i][j]
        if j-1>=0:
            left=dp[i][j-1]+M[i][j]
        else:left=dp[i-1][j]+M[i][j]
        dp[i][j]=min(up,left);
print(dp[-1][-1])