【算法】动态规划 Dynamic Programming

本文链接：https://blog.csdn.net/cxxya/article/details/100069488

参考

关于动态规划

动态规划（英语：Dynamic programming，简称DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划算法适用于有重叠子问题和最优子结构性质的问题，其所耗时间往往远少于朴素解法。
其主要思路是通过寻找最优子结构的同时记录最优子结构。对于一个给定问题，将其分解成不同部分（即子问题），一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下一次需要同一个子问题解之时直接查表——这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

其步骤分为两步：1.确定状态，2.根据状态列状态转移方程。

实例分析

数字三角形

给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。
[2],
[3, 4],
[6, 5, 7],
[4, 1, 8, 3]

确定状态
每次向下走的一步即为一个状态
状态转移方程
从上一个状态到下一个状态，如果确定最优，当前状态的结果，取决于上一个状态，找到上一个状态，然后确定上一个状态到当前状态转移的方程。记录下每一个状态，我们通过一个二维数组来实现。

public static int minimumTotal(int[][] triangle) {
    if(triangle==null||triangle.length==0)
        return 0;
    int len = triangle.length;
    // 用来记录每一步的状态
    // 这里的状态的实际意义是从起点到达三角形的某点时的最小路径
    int [][] cost = new int[len][len];
    cost[0][0]=triangle[0][0];
    for(int i=1; i<len; i++){
        for(int j=0; j<triangle[i].length; j++){
            //计算上一个状态的时候，防止出现越界问题
            //(确定上一层的相邻点（可以到当前点的点）的位置)
            int lower = Math.max(0,j-1);
            int upper = Math.min(j,triangle[i-1].length-1);
            
            System.out.println("cost[i-1][lower]=cost["+(i-1)+"]["+lower+"]");
            System.out.println("cost[i-1][upper]=cost["+(i-1)+"]["+upper+"]");
            System.out.println("triangle["+i+"]["+j+"]="+triangle[i][j]);
        
            //状态转移方程
            cost[i][j]=Math.min(cost[i-1][lower],cost[i-1][upper])+triangle[i][j];
            System.out.println("cost["+i+"]["+j+"]="+cost[i][j]);
            System.out.println();
        }
    }
    int minCost = Integer.MAX_VALUE;
    for(int k=0; k<triangle[len-1].length; k++){
        minCost = Math.min(minCost,cost[len-1][k]);
    }

    return minCost;
}