动态规划（Dynamic Programming）例题步骤详解

旧城等待， 2022-11-30 01:36 133阅读 0赞

### 文章目录 ###

*  动态规划（Dynamic Programming）浅学 - 学习笔记
 *   *  题目特点：
     *  1、选择硬币组合问题：（Coin Change）
     *  动态规划题四个核心步骤：
     *   *  一、确定状态
         *  二、转移方程
         *  三、初始条件和边界情况
         *  四、计算顺序
         *  小结：
         *  编程代码：（Java）
     *  2、多少种路径问题（Unique Paths）
     *   *  1、确定状态
         *  2、转移方程
         *  3、初始条件和边界情况
         *  4、计算顺序
         *  编程代码：（Java）
     *  3、Jump Game
     *   *  1、确定状态
         *  2、转移方程
         *  3、初始条件和边界情况
         *  4、计算顺序
         *  编程代码：（Java）
         *  总结

# 动态规划（Dynamic Programming）浅学 - 学习笔记 #

## 题目特点： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center]

## 1、选择硬币组合问题：（Coin Change） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 3]

## 动态规划题四个核心步骤： ##

### 一、确定状态 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 4]

其中，**最后一步**是指：（上面例子举例说）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 5]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 6]

其中，**子问题**是指：（上面例子举例说）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 7]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 8]

**递归解法：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 9]

**递归解法的问题：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 10]

**重复计算**，效率不高！

应当如何避免？

将计算结果保存下来（memories），并改变计算顺序。

### 二、转移方程 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 11]

### 三、初始条件和边界情况 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 12]

### 四、计算顺序 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 13]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 14]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 15]

### 小结： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 16]

### 编程代码：（Java） ###

public class Solution{ 
      					//{2,5,7} 27
      public int coinChange(int A[],int M){ 
        int[] f = new int[M+1]; //0...M
        int len = A.length;
        //初始化
        f[0] = 0;
        int i,j;
        for(i=1;i<=M;++i){ 
          f[1] = Integer.MAX_VALUE;
          //f[i] = min{f[i-A[0]]+1,...,f[i-A[len-1]]+1}
          for(j=0;j<len;++j){ 
            if(i>=A[j] && f[i-A[j]] != Integer.MAX_VALUE){  //判断条件
              f[i] = Math.min(f[i-A[j]]+1,f[i]);
            }
          }
        }
        if(f[M] == Math.MAX_VALUE){ 
          f[M] = -1;
        }
        return f[M];
      }
    }

## 2、多少种路径问题（Unique Paths） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 17]

### 1、确定状态 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 18]

**子问题：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 19]

### 2、转移方程 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 20]

### 3、初始条件和边界情况 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 21]

### 4、计算顺序 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 22]

### 编程代码：（Java） ###

public class Solution{ 
      public int uniquePaths(int m,int n){ 
        int[][] f = new int[m][n];
        int i,j;
        for(i=0;i<m;++i){  //行 从上到下
          for(j=0;j<n;++j){  //列 从左到右
            if(i=0 && j=0){ 
              f[i][j] = 1;
            }else{ 
              f[i][j] = f[i-1][j]+f[i][j-1];
            }
          }
        }
        return f[m-1][n-1];
      }
    }

## 3、Jump Game ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 23]

### 1、确定状态 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 24]

**子问题：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 25]

### 2、转移方程 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 26]

### 3、初始条件和边界情况 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 27]

### 4、计算顺序 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 28]

### 编程代码：（Java） ###

public class Solution{ 
      public boolean canJump(int[] A){ 
        int n = A.length;
        boolean[] f = new boolean[n];
        //初始化
        f[0] = true;
        int i,j;
        for(j = 1;j < n;j++){ 
          f[j] = false;
          for(i=0;i<j;i++){ 
            if(f[i] && i+A[i] >= j){ 
              f[j] = true;
              break;
            }
          }
        }
        
        return f[n-1];
      }
    }

此题若用贪心算法时间复杂度则为O(n):

**贪心算法解题思路**

这个问题可以通过递归很容易解决来处理，我们想要知道能否到达`index`，那么只需要知道`index`之前的元素是不是有`nums[i]+i >= index for i in range(index)`（也就是`index`之前是不是有位置可以到达`index`）。

public class Solution { 
        public boolean canJump(int[] nums) { 
            int reach = nums[0];
            for(int i = 1; i < nums.length && reach >= i; i++)
                if(i + nums[i] > reach) reach = i + nums[i];  //贪心策略
            return reach >= (nums.length-1) ? true : false;
        }
    }

### 总结 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 29]

此博文是在网上看了一个关于动态规划的学习视频所记录，如有问题还请指出，感谢。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/9ff7a410f27e47e083f212c95172951d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/8e80deac905a4b649b0d596ecd236e5d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/3b8a6e988586484c9f65659e3f71bb82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/aeb498e6d18e4681bcf5124dde5d1e6e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221124/b2eb0594d75d476d89f91b2051b60bbe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221124/78c316b045cd4ec18b9d6eaef8b377ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221124/5ac76e00762b48a98f58d195045ae932.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221124/d0de6bbee78a4a4fb2f3ca39e7d2e7ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221124/5430b5e061d24d34af5fdcfdbcdb0306.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221124/53201f75b90a424e97e33d1833240fb7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221124/2ec79837e20f4bb091cca22de57146df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221124/9fe3a9db27074e16a74cd1f39052f72f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221124/2012443e6d114a39ac85f3d1865f8ae0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20221124/39fcd0d763584b5c997c941eb9810917.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 14]: /images/20221124/c09e386432e44a84a15198bfb3e2e0e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 15]: /images/20221124/de9373eab54b467d8a8925a7c740a7dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 16]: /images/20221124/7fe433f7d8e94cebbc36b72ffa630bbc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 17]: /images/20221124/f31bd134e03a4458a41dc1818be3c69f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 18]: /images/20221124/4823edb951ab4bbda05a4eea819ad56f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 19]: /images/20221124/e1973f5577194369afdd4edde9b07f2f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 20]: /images/20221124/49d0e2e5f96d44b0ae4c96c1a58be8d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 21]: /images/20221124/74c8ad10f894455b81a84ecc47e47ea7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 22]: /images/20221124/61cb58b5803c4876a62f7dfc23d09f07.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 23]: /images/20221124/84879e3df71c461d84da83f7727cf34e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 24]: /images/20221124/953ee0e159ee4414bf57fa2b13a9b9df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 25]: /images/20221124/5cbd5bd17b794b88ab91fd11b563c7fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 26]: /images/20221124/d64ade967b1c4ceaaa9f16fcf206c525.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 27]: /images/20221124/8431ecda63b24303bfaba2c73a36b8d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 28]: /images/20221124/0a90bcbbed0d41f1a03c3b858452007e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 29]: /images/20221124/346943383ca64d62adb491ad60b3ddb5.png