package dp;

import org.junit.Test;

/**
 * @Author: wei1
 * @Date: Create in 2018/11/24 1:17
 * @Description: 这是一个典型的dp问题，求的dp[][]数组就ok了
 * 给你一个数组arr， 和一个整数aim。 如果可以任意选择arr中的
 * 数字， 能不能累加得到aim， 返回true或者false
 */
public class MinPath {
    public int minPath1(int[][] matrix) {
        return recursion1(matrix, 0, 0, matrix.length - 1, matrix[0].length - 1);
    }

    private int recursion1(int[][] matrix, int i, int j, int y, int x) {
        int min = matrix[i][j];
        if (i == y && j == x) {
            return min;
        }
        if (i == y && j < x) {
            return min + recursion1(matrix, i, j + 1, y, x);
        }
        if (i < y && j == x) {
            return min + recursion1(matrix, i + 1, j, y, x);
        }
        int m1 = recursion1(matrix, i, j + 1, y, x);
        int m2 = recursion1(matrix, i + 1, j, y, x);
        return min + Math.min(m1, m2);
    }

    public int minPath2(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] dp = new int[row][col];
        dp[row - 1][col - 1] = matrix[row - 1][col - 1];
        for (int i = col - 1; i > 0; i--) {
            dp[row - 1][i - 1] = matrix[row - 1][i - 1] + dp[row - 1][i];
        }
        for (int i = row - 1; i > 0; i--) {
            dp[i - 1][col - 1] = matrix[i - 1][col - 1] + dp[i][col - 1];
        }
        for (int i = row - 2; i >= 0; i--) {
            for (int j = col - 2; j >= 0; j--) {
                dp[i][j] = matrix[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
            }
        }
        return dp[0][0];
    }

    @Test
    public void test() {
        int[][] m = {
                {1, 3, 5, 9},
                {8, 1, 3, 4},
                {8, 1, 3, 4},
                {5, 0, 6, 1},
                {5, 0, 6, 1},
                {5, 0, 6, 1},
                {8, 8, 4, 0}
        };
        System.out.println(minPath1(m));
        System.out.println(minPath2(m));

    }
}