动态规划入门---通过实战Leetcode学习动态规划

通过这篇文章你能学到什么

了解动态规划的概念
入门动态规划
解决简单、中等难度的动态规划题目

什么是动态规划（Dynamic Programming）

动态规划是在解决多阶段决策过程中的一种算法，常用于解决最优问题，如：最短路径、最多、最少等。通过多阶段我们就能知道，动态规划是将一个问题分解成多个子问题，有点类似于分治算法，但不同的是动态规划每个阶段之间不是独立存在的，每个阶段会依赖上个阶段的结果，从而解出最优解。

如何拆分问题

接下来我们通过一道题来学习如何将一个问题分解成多个子问题
爬楼梯问题

题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

这道问题怎么考虑呢？首先我们自己想下前几种情况看能不能发现规律
1阶对应1种不同： 1
2阶对应2种不同： 1 1 、 2
3阶对应3种不同： 1 1 1、 1 2、 2 1
4阶对应5种不同： 1 1 1 1、1 1 2、1 2 1、2 1 1、 2 2
看到3阶的时候发现好像就是阶数，但是到了4阶发现越来越多，而且好像并没有发现什么规律。

思考
我们仔细考虑一下，题目中我们每次只能爬1或2个台阶，那如果我现在是7层，意味着只用考虑5层和6层的情况，因为4层要先到5、6才能到7。以此类推6层只用考虑5层和4层的情况、5层只用考虑4层和3层的情况。对于前几层的情况我们都是已知的。
由此问题就可以进行如下拆解：
假设： f(n)为第n层的爬法次数
可得： f(n) = f(n-1)+f(n-2)
所以代码实现：

    public int climbStairs(int n) {
        //小于3直接返回
        if (n < 3) {
            return n;
        }
        int[] dp = new int[n + 1];
        //初始化
        dp[1] = 1;
        dp[2] = 2;
        //对每个子问题求解
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

当然代码可以进行简洁优化，如：不用创建数组保存状态，因为每次只和前两有关所以只需要两个变量，和一个当前的变量即可，不过这里主要是为了方便大家理解。这里的数组

通过上面的示例相信大家对如何将问题拆分都有了一定的了解，要注意的一点是，我们拆分的每个问题都应该是有个统一的解法，也就意味着是重复的子问题。

进阶问题解决

1.最小路径和
题目：给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

相信通过上面的如何拆分问题大家看到这个题都有思路了。通过题目我们就能获得，当前位置的最小路径和只用在上和左选择最小的一个即可。如图所示，坐标(0,1)的只能选择1所以最小和为4。(1,0)只能选择1最小和为3。(1,1)只需要判断(0,1)、(1,0)谁小选谁,所以最小和为5。
最小路径和.jpeg
由此我们可以获得子问题的解法
假设: f(x,y)表示求解坐标(x,y)的最小路径和、Cxy表示(x,y)的值
可得: f(x,y) = MIN{f(x-1,y),f(x,y-1)}+Cxy
代码如下：首先初始化第一行和第一列（因为它们只有一个方向选择）

    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        //初始化第一列
        for (int i = 1; i < row; i++) {
            grid[i][0] = grid[i - 1][0] + grid[i][0];
        }
        //初始化第一行
        for (int i = 1; i < col; i++) {
            grid[0][i] = grid[0][i - 1] + grid[0][i];
        }
        //当前最小路径和
        int min;
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                //选择最小即可
                min = Math.min(grid[i - 1][j], grid[i][j - 1]);
                grid[i][j] = grid[i][j] + min;
            }
        }
        return grid[row - 1][col - 1];
    }

2.零钱兑换
题目：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1
leetcode官方示例：
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
想法

回溯算法解决：将所有情况列举出来，然后选择出数量最少的一种。但是如果我们的coins数量和amount的值非常大的时候，回溯算法的耗时就是指数级别的增加。不推荐：时间复杂度高
贪心算法解决：每次选取都选择当前能选择的最大的面额，如：第一次选择5，还剩6，第二次选择5，还剩1，第三次选择1，结束。但是贪心算法只会考虑当前的最优解，最后可能解出来的不是最优解，如面额为1 4 7。amount=12,按照贪心算法：7 1 1 1 1 1。最优解：4 4 4。所以不推荐：结果不一定是最优解
动态规划解决这道题 推荐，效率高

解决问题的关键当然是如何拆分问题，如何将问题变成多个子问题，得到状态方程。
通过上面两题的经验，我们知道只需要找和当前结果有关的前面阶段的结果即可，这也是我们前面提到的，当前阶段依赖前面阶段的结果。通过这个问题示例我们发现，当前面额n，其实我们只用注意 n-1、n-2、n-5的情况，在这三种情况中选择数量最少的一种然后+1既是f(n)的数量最小的情况。当然这道题的coins是不确定的，不过我们可以使用循环然后找出最小的即可，而每次的结果我们可以通过数组进行存储，从n=1开始直到n==amount目标的时候，就解决了。当然如果面额相等就会只需要当前一张即可，所以我们可以数组dp[0]=0，即n-coins[index]=0。
简化后的方程：f(x) = MIN{f(x-Ci)}+1 其中Ci in coins
具体实现代码如下所示：

public int coinChange(int[] coins, int amount) {
        //0直接返回
        if (amount == 0) {
            return 0;
        }
        //初始化dp数组，dp[]在dp中很常见，用于保存前面阶段的状态来解决后面的问题（备忘录）
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        int n = 1;
        //当前值
        int curr;
        //下标
        int index;
        while (n <= amount) {
            curr = Integer.MAX_VALUE;
            for (int i : coins) {
                if (n >= i) {
                    //获取前面阶段结果的下标
                    index = n - i;
                    //防止前面结果为0时被误判为相等面额
                    if (index == 0 || dp[index] != 0) {
                        curr = Math.min(curr, dp[index] + 1);
                    }
                }
            }
            if (curr != Integer.MAX_VALUE) {
                dp[n] = curr;
            }
            n++;
        }

        return dp[amount] == 0 ? -1 : dp[amount];
    }

总结

在这里主要是让大家对动态规划有个最基本的了解，还有对一些基本的动态规划问题的讲解。很多人即使明白动态规划，面对问题时也难以下手，其实主要是刷的题还不够多或难以准确的找到解决方程。在刷Leetcode的时候我们可以多看看官方题解，当题目量上来，面对问题也就能很快发现其中的关键。看完这篇文章大家不妨去试试做一道题来看自己是不是对动态规划有了点领会。传送门biu～最长上升子序列
最后本篇文章并没有很系统的讲解动态规划的一些概念，只是通过几个示例带着代价从实践出发以解决问题为主的了解动态规划。如果想系统的学习动态规划或者数据结构和算法，推荐大家看王争数据结构与算法之美

资料参考
leetcode官方