小白学习动态规划：优化篇

逃离我推掉我的手 2021-08-24 18:50 408阅读 0赞

### 目录 ###

*   *  优化类型一：一维降变量
     *  优化类型二：二维降一维
     *  总结

上一篇讲述了动态规划入门级题目，代码都是没有优化的，如果没有看过的读者也没关系，在下面会贴出这两道题目的所有代码，包括没有优化的和优化之后的。感兴趣的读者可以先去看一下上一篇的题目，都是EASY级别的题目。  
[ 小白学习动态规划：入门篇][Link 1]

今天主要是对上一篇博客的两道题目进行优化，对于绝大多数利用动态规划的算法题作优化时，个人认为最重要的优化方法就是：**画DP的图！找出状态之间的依赖关系，将其它没有依赖的状态废弃掉。**

**如果你不懂没有关系，可以看以下例子，很好理解~**

## 优化类型一：一维降变量 ##

LeetCode70. 爬楼梯

> 问题描述：假设你需要爬楼梯，需要爬n阶才能到达楼顶，每次可以爬1或2阶，由多少种不同的方法可以爬到楼顶？

**未优化前的代码：**

class Solution { 
        public int climbStairs(int n) { 
    		int[] dp = new int[n];
    		for (int i = 0; i < dp.length; i++) { 
                if(i == 0){  //第1阶
    				dp[i] = 1;
    			}else if(i == 1){  //第2阶
    				dp[i] = 2;
    			}else{  //第3阶及以上
    				dp[i] = dp[i-1]+dp[i-2];
    			}
    		}
    	    return dp[n-1];
        }
    }

首先，我们先分析dp的填充过程，观察有什么值是会在某个时间段后作废（一直没有使用到）  
![图片1][1]  
![图片2][2]  
![图片3][3]![图片4][4]  
从上面几幅图可以很清晰地观察到，从求第四阶楼梯的爬楼梯方法数之后，每求下一阶楼梯的方法数时，**就会有多一个值被废弃掉，而求某个状态的值（爬楼梯的方法数）只与它的第(n-2)个状态和第(n-1)个状态\[n >= 3\]有依赖关系**，所以在第(n-2)个状态以前的值就被废弃掉了。

> 所以，这个定义一维DP数组在某种程度上是浪费了内存空间的。

**未优化前的状态转移方程：**  
 d p \[ i \] = \{ d p \[ i − 1 \] + d p \[ i − 2 \] , i f   i ≥ 2 i i f   i < 2 dp\[i\] = \\begin\{cases\} dp\[i-1\] + dp\[i-2\],&if\\ i≥2\\\\ i &if\\ i < 2 \\end\{cases\} dp\[i\]=\{ dp\[i−1\]\+dp\[i−2\],iif i≥2if i<2  
**优化的过程可以观察下图：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70]

> **颜色的含义（帮助你理解整个过程）：**
> 
> 蓝色：初始化的状态值
> 
> 黄色：得出下一个状态的状态值
> 
> 红色：将当前状态的第(n-1)个状态转化为第(n-2)个状态
> 
> 绿色：将第n个状态转化为第(n-1)个状态

**动态规划过程：**

> **求出一个新的状态时，将当前状态的第(n-1)状态更新为第(n-2)个状态，将当前状态更新为第(n-1)个状态，继续求下一个新的状态，直到循环结束。**

**优化后的代码：**

class Solution { 
        public int climbStairs(int n) { 
            if(n <= 2){ return n;}
            int dp0 = 1;
            int dp1 = 2;
            for(int i = 3; i <= n; i++){ 
                int result = dp0 + dp1;
                dp0 = dp1;
                dp1 = result;
            }
            return dp1;
        }
    }

## 优化类型二：二维降一维 ##

LeetCode62. 不同路径

> 问题描述：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
> 
> 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
> 
> 问总共有多少条不同的路径？

![图片6][6]

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

**未优化前的代码：**

class Solution { 
        public int uniquePaths(int m, int n) { 
            int[][] dp = new int[m][n];
            for (int i = 0; i < m; i++){ 
                for (int j = 0; j < n; j++){ 
                    //上边界
                    if(i == 0 && j >= 0){ dp[i][j] = 1;continue;}
                    //左边界
                    if(j == 0 && i >= 0){ dp[i][j] = 1;continue;}
                    //其它情况
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
            return dp[m-1][n-1];
        }
    }

**观察未优化前的DP矩阵：**

![图片7][7]  
状态转移方程：  
 d p \[ i \] \[ j \] \{ d p \[ i − 1 \] \[ j \] + d p \[ i \] \[ j − 1 \] , i f   j ≥ 1   A N D   i ≥ 1 1 , i f   ( i = 0   A N D   j ≥ 0 ) O R ( i ≥ 0   A N D   j = 0 ) dp\[i\]\[j\]\\begin\{cases\}dp\[i-1\]\[j\]+dp\[i\]\[j-1\], &if\\ j≥1\\ AND\\ i≥1\\\\ 1, &if\\ (i=0\\ AND\\ j≥0)OR(i≥0\\ AND\\ j=0)\\\\ \\end\{cases\} dp\[i\]\[j\]\{ dp\[i−1\]\[j\]\+dp\[i\]\[j−1\],1,if j≥1 AND i≥1if (i=0 AND j≥0)OR(i≥0 AND j=0)  
当填充第二行时，情况是这样的：

![图片8][8]  
**当填充第三行时，情况是这样的：**  
![图片9][9]  
\*\*细心的我们会发现：\*\*第一行数据已经没有用处了，它的存在与否不影响我们求第三行的数据。所以，**我们只需要保存上一行数据，就可以得出下一行的数据，并且每求出下一行的一个数据时，都可以舍弃掉上一行的那一个数据，所以只需要一维数组保存一行数据就可以求出下一行的数据。**

**如果你不是很懂，那么看下面几幅图就会秒懂~**

**注意左边数组行下标一直为0，表示该数组本质上只有一行**  
![图片10][10]  
![图片11][11]  
原本二维dp数组的状态转移方程为：  
 d p \[ i \] \[ j \] = \{ d p \[ i − 1 \] \[ j \] + d p \[ i \] \[ j − 1 \] , i f   j ≥ 1   A N D   i ≥ 1 1 , i f   ( i = 0   A N D   j ≥ 0 ) O R ( i ≥ 0   A N D   j = 0 ) dp\[i\]\[j\]=\\begin\{cases\}dp\[i-1\]\[j\]+dp\[i\]\[j-1\], &if\\ j≥1\\ AND\\ i≥1\\\\ 1, &if\\ (i=0\\ AND\\ j≥0)OR(i≥0\\ AND\\ j=0)\\\\ \\end\{cases\} dp\[i\]\[j\]=\{ dp\[i−1\]\[j\]\+dp\[i\]\[j−1\],1,if j≥1 AND i≥1if (i=0 AND j≥0)OR(i≥0 AND j=0)  
在图中从位置上表现出来的结果是正确的，**但是！！！重点来了！**

**注意看！我们会发现状态转移方程转化为：**  
 d p \[ i \] = \{ d p \[ i − 1 \] + d p \[ i \] , i f   i ≥ 1 1 , i f   i = 0 dp\[i\]=\\begin\{cases\}dp\[i-1\]+dp\[i\], &if\\ i≥1\\\\ 1, &if\\ i=0\\\\ \\end\{cases\} dp\[i\]=\{ dp\[i−1\]\+dp\[i\],1,if i≥1if i=0

> DP的空间复杂度由O(m \* n) 降低为O(m)

最后数组就会呈现出下图得到状态：  
![图片12][12]  
**优化后的一维dp代码：**

class Solution { 
        public int uniquePaths(int m, int n) { 
            if(m <= 1 || n <= 1){ return 1;}
            int[] dp = new int[n];
            for(int i = 0; i < m; i++){ 
                for(int j = 0; j < n; j++){ 
                    if(j == 0){ dp[j] = 1;continue;}
                    dp[j] = dp[j-1] + dp[j];
                }
            }
            return dp[dp.length - 1];
        }
    }

--------------------

## 总结 ##

这两道题目虽然简单，但是它们是动态规划入门的必做题目中的两道，掌握这两道题目的思想和优化技巧是非常重要的，优化DP的核心在于：**画图**

> 掌握画图这一种优化方法，寻找值的依赖关系，观察能否将空间复杂度降低，DP的核心本质上是**用空间换取时间**的算法，在面试中会遇到许多面试官提出优化方法的场景，掌握这一种技巧，刷多一些相关的题目，自然会熟能生巧！

[Link 1]: https://blog.csdn.net/weixin_41949328/article/details/104150403
[1]: /images/20210511/e6b660d557a04b35acbe99b809d05a97.png
[2]: /images/20210511/a3fe0564291e4806912bead28ec57f9b.png
[3]: https://img-blog.csdnimg.cn/20200206093922594.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA==,size_16,color_FFFFFF,t_70
[4]: /images/20210511/9a07053eeb924abca8eb7b6d8771f4e3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk0OTMyOA_size_16_color_FFFFFF_t_70]: /images/20210511/8316163e652e4208903da3dfefeabc2c.png
[6]: /images/20210511/c3bc444a287c4c63ab30d9ac2bb7859e.png
[7]: /images/20210511/5f59955b2f3043c7b4bc5b1a7a557d0e.png
[8]: /images/20210511/44a5aff395a74811baa815d5ee0b1eb7.png
[9]: /images/20210511/39ffb0512e854e1cbe0b5077a9d67b65.png
[10]: /images/20210511/5f2e6843a2e448309cede9285133780b.png
[11]: /images/20210511/cc80573b603742b2be9f3bf77d30113a.png
[12]: /images/20210511/74686bd46da94c2d997c6f2d2f125e2e.png