动态规划 2020-03-17

动态规划

动态规划重要的是：判断状态，状态转移方程

数字三角形

问题描述
给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。

[2],
[3,4],
[6,5,7],
[4,1,8,3]

从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。

1. 定义数组元素的含义
   cost[i][j] -> 来存储到达了当前的时候的最小路径
   当到达了数组坐标 (i , j) 的时候，前面所走的结果最小值

2. 找出数组元素间的关系
   分析：
   题目中的5那个值，可以从4来，也可以从3来。

5的坐标是(2, 1)
3的坐标是(0, 1)
4的坐标是(1, 1)

通过上面得出

g(i, j) = cost[][]
定义 g 函数是最优解和的一个函数
到达5的时候 g(2,1) = min(g(0,1), g(1,1)) + f(2,1) 这个是cost这个数组所需要的函数解

然后出现一个通项式
g(i, j) = min(g(i-1, j-1), g(i-1, j)) [i>=1, j 的值要小于上一楼的下标，不然会越界，这样值可以就不对了 ]

在走到(i, j) 之前，要么是(i-1, j-1)位置，要么是(i-1, j) 位置过来的

cost[i][j] = min(cost[i-1][j-1], cost[i-1][j]) + data[i][j]
data 是原始数据

代码如下：

int[][] data = {
                {2},
                {3, 4},
                {6, 5, 7},
                {4, 1, 8, 3}};

  public static int minTotal(int[][] data) {
        if (data == null || data.length == 0) {
            return 0;
        }
        final int len = data.length;
        int[][] cost = new int[len][len];
        //todo 初始值 这个写完之后忘记给了
        cost[0][0] = data[0][0];
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < data[i].length; j++) {
                //j-1会越界
                int low = max(j - 1, 0);
                //上一排的长度一般会少于这一排，所以下标也可能越界
                int up = min(j, data[i - 1].length - 1);
                cost[i][j] = min(cost[i - 1][low], cost[i - 1][up]) + data[i][j];
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < cost[len - 1].length; i++) {
            min = min(min, cost[len - 1][i]);
        }

        return min;
    }