🌈前言?

大家好，我是耀星🌟，相信大家在学习算法时会遇到很多的问题，这些问题可能你百思不得其解，有时候想着想着就放弃了，大可不必。或许能在我的指引🚩下能找到一点光明，遇到困难咱不能畏惧😱，迎刃而上一定会有所收获🏅，当然动态规划是具有一定难度🔉，题型多，没有固定模板，但是掌握解动态规划的基本过程🔃，跟着我一起学习相信你一定会对动态规划有更深入的了解。

🚚动态规划介绍

动态规划(Dynamic Programming DP)是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果--百度百科

动态规划通常用来解决最优化问题，在解决这类问题，我们通常使用一组选择来达到最优解。在做出每次选择时，通常会生成与原问题形式相同的子问题。当有N（N>1）个子问题都生成相同的子问题时，动态规划技术通常就会变的非常有效，关键技术对于每一个子问题都能保存其解，当其重复出现时即可避免重复求解。这些话看起来比较抽象，博主会通过一些简单的例子带大家入门。

🔗动态规划与递归的关系

大家在学习动态规划之前，有必要了解动态规划和递归的关系，动态规划和递归非常的相似，都是通过组合子问题的解来求解原问题，且一般递归的问题都可以转化为动态规划，咱们举个简单的例子👇斐波那契数列?。

Example 1:斐波那契数列

第i个斐波那契数列值F[i]=F[i-1]+F[i-2]，如果我们想知道F[n]，那么我们就必须要知道F[n-1]和F[n-2]的值，如果采用递归的思路，将F[n]拆分成求F[n-1]+F[n-2]，将原问题拆分成子问题求解，不同的子问题又有公共的子子问题。采用递归会做许多不必要的重复计算。例如求解F[5]:

?从图中我们可以看到，F[3]和F[1]被重复计算了两次，F[2]被重复计算3次，如果要计算很多运行的效率会非常慢。我们仅仅计算F[5]就开辟了9个栈区，如果F[100]呢大概需要开辟2^99个栈区(StackOverFlow)

//递归求斐波那契数列的第N项
public static long Fac(int n)
{
    if(n == 1 || n == 2)
    {
        return 1;
    }

    return Fac(n-1) + Fac(n-2);
}

那么我们需要如何使用动态规划来解决这个问题呢？

对于每一个子问题都能保存其解，把每次计算出来的值用dp[i]数组保存起来。

i:表示第i个元素

dp[i]:表示第i个元素的值

public static long Fac(int n)
{
    if(n <= 2)
    {
        return 1;
    }
 
    long dp[100] = {0};
    
    //初始化第一个元素和第二个元素
    dp[1] = 1;
    dp[2] = 1;
    
    int i = 0;
    for(i = 3; i <= n; i++)
    {
        dp[i] = dp[i-1] + dp[i-2];
    }
    
    return dp[n];
}

是否能够继续优化呢？

当我们计算dp[i]时，只需要知道dp[i-1]和dp[i-2]，可以利用两个局部变量来保存preFistt=dp[i-1]和preSecond=dp[i-2]的值，如果你想计算dp[i+1]，则改变preFirst=dp[i]，preSecond=dp[i-1]依次类推。

public static long Fac(int n)
{
    if(n <= 2)
    {
        return 1;
    }
    
    //初始化
    int preFirst = 1;//preFirst = dp[i-1]
    int preSecond = 1;//preSecond = dp[i-2]
    int ans = 0;//ans = dp[i]

    int i = 0;
    for(i =3; i <= n; i++)
    {
        ans = preFirst + preSecond;
        preSecond = preFirst;
        preFirst = ans;
    }

    return ans;
}

?Example 2:走迷宫，只能向右或者向下走，小人能够到达终点的有多少种走法？

设有n行m列，想要走到(n,m)，我们只需要知道走到X=Labyrinth(n-1,m)和Y=Labyringth(n,m-1)有多少种方法，Labyrinth(n,m)=X+Y，将原问题划分为求子问题的解，就可以通过使用递归来进行计算。

public static int Labyrinth(int n, int m)
{
    if(m == 1 && n == 1)
    {
        return 1;
    }
    
    //处理边界情况
    if(m == 1 || n == 1)
    {
        return 1;
    }

    return Labyrinth(m-1, n) + Labyrinth(m, n-1);
}

?使用递归同样存在着容易栈溢出的问题，那么我们如何使用动态规划来解决这个问题呢，使用一个dp[n][m]数组，将走到每一个方格的走法记录下来。

n:表示第n行

m:表示第m列

dp[n][m]:表示走到第n行第m列有多少种方法？

说明：从第0行和第0列，所有最后得到的结果储存dp[n-1][m-1]内。?


public static int Labyrinth(int m, int n){
        int[][] dp = new dp[n][m];
        //初始化
        dp[0][0] = 1;
        
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(i == 0 || j == 0){
                    dp[i][j] = 1;
                }

                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        
        return dp[n-1][m-1];
}

我们还可以继续进行优化，我们可以发现我们计算dp[n-1][m-1] = dp[n-2][m-1]+dp[n-1][m-2]时只需要用到第n-1行和n-2行的元素的值，因此我们就可以用一个n=2，m=m的滚动二维数组进行计算。

public static int Labyrinth(int m, int n){
        int[][] dp = new int[2][m];
        //初始化
        dp[0][0] = 1;
      
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(i == 0 || j == 0){
                    dp[i%2][j] = 1;
                    continue;
                }

                if(i%2 == 0)//偶数行用1行的元素
                	dp[i%2][j] = dp[i%2][j-1] + dp[i%2+1][j];
                else//奇数行用第0行的元素
                	dp[i%2][j] = dp[i%2][j-1] + dp[i%2-1][j];
                
            }
        }
        return dp[(n+1)%2][m-1];
}

Example 3:?现在考虑网格中有障碍物，那样将会有多少条不同的路径？

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

LintCode链接：不同路径

我们用相同的思想推理：可以得到如下分段函数。

处理特殊情况：当起点和终点有障碍物时，走到终点的的方法为0。

public class Solution {
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // write your code here
        int n = obstacleGrid.length;//获取行
        int m = obstacleGrid[0].length;//获取列

        if (m == 0 || n == 0) {
            return 0;
        }

        int[][] dp = new int[n][m];
        
        //处理特殊情况
        if (obstacleGrid[0][0] == 1 || obstacleGrid[n - 1][m - 1] == 1) {
            return 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    if (i == 0 && j == 0) {
                        dp[i][j] = 1;
                    } else {
                        if (i == 0) {
                            dp[i][j] = dp[i][j - 1];
                        } else {
                            if (j == 0) {
                                dp[i][j] = dp[i - 1][j];
                            } else {
                                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                            }
                        }
                    }
                }
            }
        }
        return dp[n - 1][m - 1];
    }
}

📋动态规划的基本步骤?

1.确定状态

🚩状态在动态规划中的作用至关重要

🚩解动态规划一般要开辟一个数组，我们要明确第知道数组中每个元素dp[i]或者dp[i][j]代表什么。

🚩确定状态的两个意识

? ? ?最后一步

? ? ?子问题

2.列转移方程

3.初始条件和边界情况

4.计算顺序

Example 4:给定一个只含非负整数的n*m的网格，找到一条从左上角到右下角的可以使数字和最小的路径。

LintCode链接：最小路径和

?1.确定状态

最优策略的路径总和数字最小

🌈若倒数第二步在(m-2, n-1)，则前面一定是从(0,0)到达(m-2,n-1)总和最小的路径

🌈若倒数第二步在(m-1, n-2)，则前面一定是从(0,0)到达(m-1, n-2)总和最小的路径

👦子问题：要求从左上角走到(m-2, n-1)和走到(m-1, n-2)的最小路径之和

👵原问题：要求走到(m-1, n-1)的最小路径之和。

?状态：设从(0，0)走到(i, j)的最小和路径是dp[i][j]

2.转移方程

👉说明：A[i][j]代表方格中的值

3.初始条件和边界情况

💭初始条件：

dp[i][j] = A[0][0]

🌎边界情况：

当i == 0时?dp[i][j] = dp[i][j-1] + A[i][j]

当j == 0时 dp[i][j] = dp[i-1][j] + A[i][j]

4.计算顺序

dp[0][0] dp[0][1] dp[0][2] ...dp[0][m-2] dp[0][m-1]

dp[1][0]?dp[1][1] dp[1][2] ...dp[1][m-2] dp[1][m-1]

.......

dp[n-1][0]?dp[n-1][1] ...dp[n-1][m-2] dp[n-1][m-1]

5.空间优化

当我们计算第i行时，只需要用到第i行和第i-1行，那么我们就可以用一个滚动数组实现，有效的节省空间。

计算第0行，处于边界情况，只需要该行就可以计算

计算第1行，只需要用到第0行

计算第2行，只需要用到第1行，删掉第0行，

计算第3行，只需要用到第2行，删掉第1行

....

public class Solution {
    /**
     * @param grid: a list of lists of integers
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    public int minPathSum(int[][] grid) {

        int n = grid.length;
        int m = grid[0].length;

        int[][] dp = new int[2][m];//开辟滚动数组

        int old = 0;
        int now = 1;

        int t1, t2;
        for(int i=0; i<n; i++){
            //old and now swap
            now = old;
            old = 1-now;

            for(int j=0; j<m; j++){
                if(i == 0 && j == 0){
                    dp[now][j] = grid[i][j];
                    continue;
                }

                dp[now][j] = grid[i][j];
                if(i > 0){
                    t1 = dp[old][j];
                }else{
                    t1 = Integer.MAX_VALUE;//i=0时，该行的上面元素为无穷大
                }

                if(j>0){
                    t2 = dp[now][j-1];
                }else{
                    t2 = Integer.MAX_VALUE;//j=0时，该行的左边元素为无穷大
                }
                
                //选择较小的值到dp[now][j]
                if(t1 > t2){
                    dp[now][j] += t2;
                }else{
                    dp[now][j] += t1;
                }

            }
        }
        return dp[now][m-1];
    }
}

?小结

↘求最值型动态规划

↘动态规划组成部分

? ? ? -1.确定状态

? ? ? ? ? 🛑最后一步（最优策略中最后需要走的一步）

? ? ? ? ? 🛑化成子问题

? ? ? -2.转移方程

? ? ? ? ? 🛑dp[i][j]=min{dp[i-1][j]+A[i][j],dp[i][j-1]+A[i][j]}

? ? ? -3初始条件

? ? ? ? ? 🛑dp[0][0]=A[0][0]

? ? ? -4计算顺序

? ? ? ? dp[0][0] dp[0][1]....

空间优化