深圳幻海软件技术有限公司 欢迎您！
更多

动态规划入门篇

2023-03-31

int 问题 dp
目录        🌈前言         🚚动态规划介绍     &nbs

目录

        🌈前言 

        🚚动态规划介绍

        🔗动态规划与递归的关系

        📋动态规划的基本步骤 

🌈前言 

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

🚚动态规划介绍

动态规划(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)

  1. //递归求斐波那契数列的第N项
  2. public static long Fac(int n)
  3. {
  4.     if(n == 1 || n == 2)
  5.     {
  6.         return 1;
  7.     }
  8.  
  9.     return Fac(n-1) + Fac(n-2);
  10. }

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

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

i:表示第i个元素

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

  1. public static long Fac(int n)
  2. {
  3.     if(n <= 2)
  4.     {
  5.         return 1;
  6.     }
  7.  
  8.     long dp[100] = {0};
  9.     
  10.     //初始化第一个元素和第二个元素
  11.     dp[1] = 1;
  12.     dp[2] = 1;
  13.     
  14.     int i = 0;
  15.     for(i = 3; i <= n; i++)
  16.     {
  17.         dp[i] = dp[i-1] + dp[i-2];
  18.     }
  19.     
  20.     return dp[n];
  21. }

是否能够继续优化呢？

当我们计算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]依次类推。

  1. public static long Fac(int n)
  2. {
  3.     if(n <= 2)
  4.     {
  5.         return 1;
  6.     }
  7.     
  8.     //初始化
  9.     int preFirst = 1;//preFirst = dp[i-1]
  10.     int preSecond = 1;//preSecond = dp[i-2]
  11.     int ans = 0;//ans = dp[i]
  12.  
  13.     int i = 0;
  14.     for(i =3; i <= n; i++)
  15.     {
  16.         ans = preFirst + preSecond;
  17.         preSecond = preFirst;
  18.         preFirst = ans;
  19.     }
  20.  
  21.     return ans;
  22. } 
  23.

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

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

  1. public static int Labyrinth(int n, int m)
  2. {
  3.     if(m == 1 && n == 1)
  4.     {
  5.         return 1;
  6.     }
  7.     
  8.     //处理边界情况
  9.     if(m == 1 || n == 1)
  10.     {
  11.         return 1;
  12.     }
  13.  
  14.     return Labyrinth(m-1, n) + Labyrinth(m, n-1);
  15. }
  16.

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

n:表示第n行

m:表示第m列

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

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

  1.  
  2. public static int Labyrinth(int m, int n){
  3.         int[][] dp = new dp[n][m];
  4.         //初始化
  5.         dp[0][0] = 1;
  6.         
  7.         for(int i=0; i<n; i++){
  8.             for(int j=0; j<m; j++){
  9.                 if(i == 0 || j == 0){
  10.                     dp[i][j] = 1;
  11.                 }
  12.  
  13.                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
  14.             }
  15.         }
  16.         
  17.         return dp[n-1][m-1];
  18. }

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

  1. public static int Labyrinth(int m, int n){
  2.         int[][] dp = new int[2][m];
  3.         //初始化
  4.         dp[0][0] = 1;
  5.       
  6.         for(int i=0; i<n; i++){
  7.             for(int j=0; j<m; j++){
  8.                 if(i == 0 || j == 0){
  9.                     dp[i%2][j] = 1;
  10.                     continue;
  11.                 }
  12.  
  13.                 if(i%2 == 0)//偶数行用1行的元素
  14.                 dp[i%2][j] = dp[i%2][j-1] + dp[i%2+1][j];
  15.                 else//奇数行用第0行的元素
  16.                 dp[i%2][j] = dp[i%2][j-1] + dp[i%2-1][j];
  17.                 
  18.             }
  19.         }
  20.         return dp[(n+1)%2][m-1];
  21. }

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

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

LintCode链接：不同路径

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

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

  1. public class Solution {
  2.     /**
  3.      * @param obstacleGrid: A list of lists of integers
  4.      * @return: An integer
  5.      */
  6.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  7.         // write your code here
  8.         int n = obstacleGrid.length;//获取行
  9.         int m = obstacleGrid[0].length;//获取列
  10.  
  11.         if (m == 0 || n == 0) {
  12.             return 0;
  13.         }
  14.  
  15.         int[][] dp = new int[n][m];
  16.         
  17.         //处理特殊情况
  18.         if (obstacleGrid[0][0] == 1 || obstacleGrid[n - 1][m - 1] == 1) {
  19.             return 0;
  20.         }
  21.         for (int i = 0; i < n; i++) {
  22.             for (int j = 0; j < m; j++) {
  23.                 if (obstacleGrid[i][j] == 1) {
  24.                     dp[i][j] = 0;
  25.                 } else {
  26.                     if (i == 0 && j == 0) {
  27.                         dp[i][j] = 1;
  28.                     } else {
  29.                         if (i == 0) {
  30.                             dp[i][j] = dp[i][j - 1];
  31.                         } else {
  32.                             if (j == 0) {
  33.                                 dp[i][j] = dp[i - 1][j];
  34.                             } else {
  35.                                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  36.                             }
  37.                         }
  38.                     }
  39.                 }
  40.             }
  41.         }
  42.         return dp[n - 1][m - 1];
  43.     }
  44. }

📋动态规划的基本步骤 

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行

....

  1. public class Solution {
  2.     /**
  3.      * @param grid: a list of lists of integers
  4.      * @return: An integer, minimizes the sum of all numbers along its path
  5.      */
  6.     public int minPathSum(int[][] grid) {
  7.  
  8.         int n = grid.length;
  9.         int m = grid[0].length;
  10.  
  11.         int[][] dp = new int[2][m];//开辟滚动数组
  12.  
  13.         int old = 0;
  14.         int now = 1;
  15.  
  16.         int t1, t2;
  17.         for(int i=0; i<n; i++){
  18.             //old and now swap
  19.             now = old;
  20.             old = 1-now;
  21.  
  22.             for(int j=0; j<m; j++){
  23.                 if(i == 0 && j == 0){
  24.                     dp[now][j] = grid[i][j];
  25.                     continue;
  26.                 }
  27.  
  28.                 dp[now][j] = grid[i][j];
  29.                 if(i > 0){
  30.                     t1 = dp[old][j];
  31.                 }else{
  32.                     t1 = Integer.MAX_VALUE;//i=0时，该行的上面元素为无穷大
  33.                 }
  34.  
  35.                 if(j>0){
  36.                     t2 = dp[now][j-1];
  37.                 }else{
  38.                     t2 = Integer.MAX_VALUE;//j=0时，该行的左边元素为无穷大
  39.                 }
  40.                 
  41.                 //选择较小的值到dp[now][j]
  42.                 if(t1 > t2){
  43.                     dp[now][j] += t2;
  44.                 }else{
  45.                     dp[now][j] += t1;
  46.                 }
  47.  
  48.             }
  49.         }
  50.         return dp[now][m-1];
  51.     }
  52. }

 小结

↘求最值型动态规划

↘动态规划组成部分

      -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]....

空间优化

大家如果觉得有什么问题的话也可以私信我，可以和我共同讨论💬，一起学习 ！

感谢大家的支持💪！

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览42577 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪