LeetCode题解——动态规划（一）

本是古典何须时尚 2023-06-27 06:13 38阅读 0赞

### 文章目录 ###

*   *  70. 爬楼梯
     *   *  动态规划
     *  198. 打家劫舍
     *   *  动态规划1
         *  动态规划2
     *  213. 打家劫舍 II
     *   *  动态规划
     *  64. 最小路径和
     *   *  动态规划
     *  62. 不同路径
     *   *  动态规划
         *   *  推荐阅读

## 70. 爬楼梯 ##

假设你正在爬楼梯。需要 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 阶

### 动态规划 ###

定义一个数组 dp 存储上楼梯的方法数（为了方便讨论，数组下标从 1 开始），dp\[i\] 表示走到第 i 个楼梯的方法数目。

第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。  
动态转移方程为：  
`dp[i] = dp[i-1] + dp[i-2]`

考虑到 dp\[i\] 只与 dp\[i - 1\] 和 dp\[i - 2\] 有关，因此可以只用两个变量来存储 dp\[i - 1\] 和 dp\[i - 2\]，使得原来的 O(N) 空间复杂度优化为 O(1) 复杂度。

class Solution {
        
        public int climbStairs(int n) {
        
            if (n <= 2) {
        
                return n;
            }
            int pre1 = 1, pre2 = 2;
            for (int i = 2; i < n; ++i) {
        
                int cur = pre1 + pre2;
                pre1 = pre2;
                pre2 = cur;
            }
            return pre2;
        }
    }

## 198. 打家劫舍 ##

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: \[1,2,3,1\]  
输出: 4  
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。  
偷窃到的最高金额 = 1 + 3 = 4 。  
示例 2:

输入: \[2,7,9,3,1\]  
输出: 12  
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。  
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

### 动态规划1 ###

import java.lang.Math;
    import java.util.*;
    class Solution {
        
        public int rob(int[] nums) {
        
            int n = nums.length;
            int[] dp = new int[n];
            if (n == 0) {
        
                return 0;
            }
            if (n == 1) {
        
                return nums[0];
            }
            if (n == 2) {
        
                return Math.max(nums[1], nums[0]);
            }
            dp[0] = nums[0];
            dp[1] = nums[1];
            for (int i = 2; i < n; ++i) {
        
                if (i == 2) {
        
                    dp[i] = nums[i] + dp[i - 2];
                } else {
        
                    dp[i] = nums[i] + Math.max(dp[i-2], dp[i-3]);
                }
            }
            return Math.max(dp[n-1], dp[n-2]);
        }
    }

### 动态规划2 ###

![format_png][]

class Solution {
        
        public int rob(int[] nums) {
        
            int preMax = 0;
            int curMax = 0;
            for(int x : nums) {
        
                int temp = curMax;
                curMax = Math.max(preMax + x, curMax);
                preMax = temp;
            }
            return curMax;
        }
    }

## 213. 打家劫舍 II ##

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: \[2,3,2\]  
输出: 3  
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。  
示例 2:

输入: \[1,2,3,1\]  
输出: 4  
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。  
偷窃到的最高金额 = 1 + 3 = 4 。

### 动态规划 ###

class Solution {
        
        private int rob(int[] nums, int first, int last) {
        
            int pre1 = 0, pre2 = 0;
            for(int i = first; i <= last; ++i) {
        
                int cur = Math.max(pre2, pre1 + nums[i]);
                pre1 = pre2;
                pre2 = cur;
            }
            return pre2;
        }
        public int rob(int[] nums) {
        
            if (nums == null || nums.length == 0) {
        
                return 0;
            }
            int n = nums.length;
            if (n == 1) {
        
                return nums[0];
            }
            return Math.max(rob(nums, 0, n-2), rob(nums, 1, n-1));
        }
    }

## 64. 最小路径和 ##

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:  
\[  
\[1,3,1\],  
\[1,5,1\],  
\[4,2,1\]  
\]  
输出: 7  
解释: 因为路径 1→3→1→1→1 的总和最小。

### 动态规划 ###

这种方法时间复杂度为O(mn),空间复杂度也为O(mn）。还可以不用开辟一个二维数组，直接在原数组上做动态规划，空间复杂度降为O(1)。还有一种方法，空间复杂度为O(n)， `dp(j)=grid(i,j)+min(dp(j),dp(j+1))`从右下角开始遍历，每次更新dp\[j\]即可。

class Solution {
        
        public int minPathSum(int[][] grid) {
        
            if (grid == null || grid.length == 0 || grid[0].length == 0) {
        
                return 0;
            }
            int m = grid.length, n = grid[0].length;
            if (n == 1) {
        
                return grid[0][0];
            }
            int[][] result = new int[m][n];
            result[0][0] = grid[0][0];
            for (int i = 1; i < n; ++i) {
        
                result[0][i] = grid[0][i] + result[0][i-1];
            }
            for (int i = 1; i < m; ++i) {
        
                result[i][0] = grid[i][0] + result[i-1][0];
            }
            for (int i = 1; i < m; ++i) {
        
                for (int j = 1; j < n; ++j) {
        
                    result[i][j] = Math.min(grid[i][j] + result[i-1][j], grid[i][j] + result[i][j-1]); 
                }
            }
            return result[m-1][n-1];
        }
    }

## 62. 不同路径 ##

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

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

问总共有多少条不同的路径？  
![format_png 1][]

例如，上图是一个7 x 3 的网格。有多少可能的路径？

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

示例 1:

输入: m = 3, n = 2  
输出: 3  
解释:  
从左上角开始，总共有 3 条路径可以到达右下角。

1.  向右 -> 向右 -> 向下
2.  向右 -> 向下 -> 向右
3.  向下 -> 向右 -> 向右  
    示例 2:

输入: m = 7, n = 3  
输出: 28

### 动态规划 ###

每一个位置只能从左边一格或者上方一格走到，所以动态方程为`dp[i][j] = dp[i-1][j] + dp[i][j-1]`  
又因为二维dp数组，可以被一维dp数组代替，之前的数据可以不保存，动态方程优化为`dp[i]=dp[i]+d[i-1]`.

class Solution {
        
        public int uniquePaths(int m, int n) {
        
            int[] dp = new int[n];
            Arrays.fill(dp, 1);
            for (int i = 1; i < m; ++i) {
        
                for (int j = 1; j < n; ++j) {
        
                    dp[j] = dp[j] + dp[j - 1];
                }
            }
            return dp[n - 1];
        }
    }

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

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]
 *  [机器学习与深度学习核心知识点总结][Link 4]

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

欢迎关注我的公众号“**神经网络与自然语言处理**”，原创技术文章第一时间推送。

![format_png 2][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9GaWgxdTFkRXBBWWMwOXRKMzloQm5tWTdRU1ls?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9GdmRJQTQ2OEw3cUI2OURXT1lvRVJsb2hOenJs?x-oss-process=image/format,png
[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[Link 4]: https://mp.weixin.qq.com/s/QaMWxVHDf08n_3QJXbQBWQ
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9GaGwyRXlvT0hyTldRcjhHSE9fdUE3d2JYNFpI?x-oss-process=image/format,png