浅谈动态规划

如标题所示，直接进入正题吧！

---

---

概念

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，其所耗时间往往远少于朴素解法。
它的基本思想非常简单。若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，具有天然剪枝的功能，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
常见的例子是斐波那契数列：

即给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。很多问题的解法和这个式子很类似，那么接下来以几道题来简单理解下动态规划吧。

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs

这个题目在高中数学的排列组合和数列里面是出现过的，一次只能走一阶或者两阶，我们得找规律。
如果设 F[ i ] 是你走到 i 阶时的办法数，那么你如何到 n 阶处呢？那只有两种方法，从 n-1 处迈一步和从 n-2 处迈两步，此时可以很容易地得到递推表达式

再根据初始条件就可以求出任意一项了。
当然也可以根据递推表达式得到通项公式。

具体的程序就不展示了，来看下一题吧

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

image.png

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths

这个题在高中的排列组合里面也是有通项公式的

简单来说就是，在题设条件下，在一个固定的图 m x n 中，无论怎么走，向下和向右的步数是固定的。一共需要走 m + n 步，向下需要 m - 1 步，向右有 n - 1 步，剩下的就是如何组合罢了。
当然，这里重点是用动态规划的思想解决。
设 为到达处的方法数，在不考虑边界的情况，到达处的方法有俩种，从向右和从处向下，那么到达处的方法数为两处的方法数和，递推公式为：

对于边界的处理方式之一是分情况，如下：

汇总一下便是：

有了这个递推公式，我们很容易解决问题了

class Solution {
public:
    int uniquePaths(int m, int n) {
        //动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
        if(m==0||n==0){
            return 0;
        } 
        vector<vector<int>> dp(m,vector<int>(n));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0||j==0){
                    dp[i][j]=1;
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};

当然这个题也只有动态规划一种方法，递归，使用通项公式都是可以的，但是动态规划无疑是一种很优异的方法。

不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

image.png

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2

解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths-ii

这个题是上一个题的改进，增加了障碍物。
参考前一题的路径：

考虑到障碍物，对于不同情况，有
对于
当该点为障碍物的时候会导致路径为０(也会导致网络中任意一点，路径均为０)
对于
当该点为障碍物的时候导致路径为０，否则可以上方到达，所以和其上方一点的路径相同
对于
当该点为障碍物的时候导致路径为０，否则可以左方到达，所以和其左方一点的路径相同
对于
当该点为障碍物的时候导致路径为０，否则可以从上方或左方到达，因此为这两个方向的路径之和
代码如下：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        if (n < 1 || n < 1) 
            return 0;
        long long dp[m][n];  //　使用long long防止溢出
        if (obstacleGrid[0][0] == 1) return 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                if (i == 0 && j == 0){
                    //这里没有障碍物，因此路径为１
                    dp[i][j] = 1;
                } else if(i != 0 && j == 0){
                    //最左侧边界，如果该点是障碍物，则该点不可达，否则路径和达到其上侧的路径一样
                    dp[i][j] = ( obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j]);
                } else if(i == 0 && j != 0){ 
                    //最上层边界，如果该点是障碍物，则该点不可达，否则路径和达到其左侧的路径一样 
                    dp[i][j] = ( obstacleGrid[i][j] == 1 ? 0 : dp[i][j - 1]);
                } else { 
                    //对于不在边界点，仅在该点为障碍物的时候不可达   
                    dp[i][j] = ( obstacleGrid[i][j] == 1  ? 0 : dp[i][j - 1] + dp[i - 1][j]);
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

有关动态规划的部分就暂时介绍到这了，之后可能会继续更新动态规划相关内容。