码海- 动态规划

原文链接🔗

什么是动态规划？
动态规划（dynamic programming，简称 dp)是一种多阶段决策最优解模型，一般用来求最值问题，多数情况下它可以采用自下而上的递推方式来得出每个子问题的最优解（即最优子结构），进而自然而然地得出依赖子问题的原问题的最优解。

• 多阶段决策， 意味着问题可以分解成子问题，子子问题，。。。，也就是说问题可以拆分成多个子问题进行求解

• 最优子结构，自下而上的递推过程中，我们求得的每个子问题一定是全局最优解，既然它分解的子问题是全局最优解，那么依赖它们解的原问题自然也是全局最优解。

• 自下而上，怎样才能自下而上的求出每个子问题的最优解，可以肯定子问题之间是有一定联系的，即迭代递推公式，也叫「状态转移方程」，要定义好这个状态转移方程，我们就需要定义好每个子问题的状态（DP状态），那为啥要自下而上求解？因为如果采用像递归这种自顶向下的求解方式，子问题之间可能存在大量的重叠，大量地重叠子问题意味着大量的重复计算，这样时间复杂度很可能呈指数级上升（在下文中我们会看到多个这样重复的计算导致的指数级时间复杂度），所以自下而上的求解方式可以消除叠子问题。

当问题的定义是求最值问题，且问题可以采用递归的方式，并且递归的过程中有大量重复子问题的时候，基本可以断定问题可以用动态规划求解，于是我们得出了求解动态规划基本思路如下（解题四步曲）

1. 判断是否可用递归来解，可以的话进入步骤 2
2. 分析在递归的过程中是否存在大量的重复子问题
3. 采用备忘录的方式来存子问题的解以避免大量的重复计算（剪枝）
4. 改用自底向上的方式来递推，即动态规划

example:

1
2
3

节点到最底部节点的最短路径只需要求左右两个节点到最底部的最短路径两者的最小值再加此节点本身！

DP[i,j] = min(DP[i+1, j], D[i+1, j+1]) + triangle[i,j]

privatestaticint[][] triangle = {
        {2, 0, 0, 0},
        {3, 4, 0, 0},
        {6, 5, 7, 0},
        {4, 1, 8, 3}
};
public static int traverse() {
    int ROW = 4;
    int[] mini = triangle[ROW - 1];
    // 从倒数第二行求起，因为最后一行的值本身是固定的
    for (int i = ROW - 2; i >= 0; i--) {
        for (int j = 0; j < triangle[j].length; j++) {
            mini[j] = triangle[i][j] + Math.min(mini[j], mini[j+1]);
        }
    }
    return mini[0];
}

public static  void main(String[] args)  throws Throwable {
    int minPathSum = traverse();
    System.out.println("sum = " + minPathSum);
}

总结：仔细回想一下我们的解题思路，我们先看了本题是否可用递归来解，在递归的过程中发现了有重叠子问题，于是我们又用备忘录来消除递归中的重叠子问题，既然我们发现了此问题可以用递归+备忘录来求解，自然而然地想到它可以用自底向上的动态规划来求解。是的，求解动态规划就按这个套路来即可，最重要的是要找出它的状态转移方程，这需要在自下而上的推导中仔细观察。