数据结构与算法学习——动态规划-1
目录
目录
博主介绍
动态规划
1.1、概念说明
1.2、使用最小花费爬楼梯
2.3、不同路径
2.4、不同路径 II
2.5、整数拆分
2.6、不同的二叉搜索树
2.7、分割等和子集
2.8、最后一块石头的重量 II
2.9、最长递增子序列
2.10、打家劫舍
2.11、打家劫舍 II
2.12、买卖股票的最佳时机
💫点击直接资料领取💫
目录
博主介绍
💂 个人主页:苏州程序大白
💂 个人社区:CSDN全国各地程序猿
🤟作者介绍：中国DBA联盟(ACDU)成员，CSDN全国各地程序猿（媛）聚集地管理员。目前从事工业自动化软件开发工作。擅长C#、Java、机器视觉、底层算法等语言。2019年成立柒月软件工作室，2021年注册苏州凯捷智能科技有限公司
💬如果文章对你有帮助，欢迎关注、点赞、收藏（一键三连）和C#、Halcon、python+opencv、VUE、各大公司面试等一些订阅专栏哦
💅 有任何问题欢迎私信，看到会及时回复
👤 微信号：stbsl6，微信公众号：苏州程序大白
🎯 想加入技术交流群的可以加我好友，群里会分享学习资料
动态规划
1.1、概念说明
动态规划，即 Dynamic Programming ，简称 DP ，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
动态规划中每一个状态一定是由上一个状态推导出来的。
遍历顺序的确定。
对于遍历顺序，我们只需要确定两点：
1、遍历的过程中，所需的状态必须是已经计算出来的。
2、遍历的终点必须是存储结果的那个位置。
1.2、使用最小花费爬楼梯
1、题目描述
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。 每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。 请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例一：
输入：cost = [10, 15, 20] 输出：15 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15
示例二：
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出：6 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
2、解题思路
我们首先需要确定 dp 数组中元素的含义，在这道题中 dp[i] 表示到第 i 个台阶需要花费的最少的体力数，且 dp[i] 由 dp[i - 1] 和 dp[i - 2] 决定，我们由示例二可以推导出递推公式，即：
dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]
为什么递推公式中需要加的值为 dp[i] ，这是因为由题意可知，当我们爬上第 i 个楼梯时，就要花费对应的体力值，所以，到达第 i 个体力值需要支付的体力为 cost[i]。
同时我们需要注意，最后到达终点的那一步是不需要花费体力的。
3、解题代码
未进行优化前
public int minCostClimbingStairs(int[] cost) { if (cost == null || cost.length == 0) return 0; // 创建 dp 数组 int[] dp = new int[cost.length]; // 对 dp 数组中的元素进行初始化，到达第一个台阶所花费的体力为 cost[0] ，到达第二个台阶所花费的最小体力为 cost[1] // dp[1] < dp[0] + dp[1] dp[0] = cost[0]; dp[1] = cost[1]; // 进行状态转移， dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i] for (int i = 2;i < cost.length;i++) { dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i]; } // 注意，由于最后一步，即从倒数第二部到重点的过程中是不用花费体力的，所以我们要进行选择 // 看是从 cost.length - 2 步一下走两步到达终点花费的体力少，还是从 cost.length - 1 步一步到位花费的体力少 return Math.min(dp[cost.length - 1], dp[cost.length - 2]); }
在这道题中，由于 dp[i] 只由前面两个状态的值与所给的 cost[i] 决定，所以我们可以不用使用一整个数组，而是使用两个变量进行滚动更新。
使用两个变量进行滚动优化
public int minCostClimbingStairs(int[] cost) { if (cost == null || cost.length == 0) return 0; // 使用两个变量进行滚动，其中 one 表示 i - 2 ，second 表示 i - 1 int one = cost[0]; int two = cost[1]; // 在这个循环中，进行状态转移 for (int i = 2;i < cost.length;i++) { int result = Math.min(one, two) + cost[i]; // 将原本为 i - 1 位置的值赋给 one one = two; // 将当前位置的值赋值给 two two = result; } // 同理，这里最后也不能返回 result ，而是需要在 one 和 two 之间做出选择 return Math.min(one, two); }
2.3、不同路径
1、题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？
示例一：
输入：m = 3, n = 7 输出：28
示例二
输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下
2、解题思路
确定 dp 数组
在这个问题中，我们需要一个二维的 dp 数组，其中 dp[i][j] 表示到达网格第 i 行第 j 列的方法数
确定状态转移方程
由于机器人只能向右走或者向下走，所以到达网格第 i 行第 j 列的方法数 dp[i][j] 应该为到达它左边的方格的方法数与到达它上边的方格的方法数之和。 所以，我们可以得到它的状态转移方程为：
由于机器人只能向右走或者向下走，所以到达网格第 i 行第 j 列的方法数 dp[i][j] 应该为到达它左边的方格的方法数与到达它上边的方格的方法数之和。 所以，我们可以得到它的状态转移方程为：
// dp[i - 1][j] 为 dp[i][j] 的上边方格 // dp[i][j - 1] 为 dp[i][j] 的左边方格 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
确定 base case
对于第一行第一列上的网格而言，机器人只有一种方法到达该网格， 即一直向右走 / 往下走，这种网格我们需要对其进行初始化
3、解题代码
public int uniquePaths(int m, int n) { // 进行参数校验 if (m <= 0 || n <= 0) return 0; // 创建一个 dp 数组，其中 dp[i][j] 表示到达网格第 i 行第 j 列处可以使用的方法数 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) { // 当 i == 0 或者 j == 0 时，代表在网格的第一行或者第一列，这种情况下，机器人只有一种方法到达 dp[i][j] = 1; } else { // 当 i 与 j 均不为 0 时，此时要进行状态转移 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } // 返回 dp 数组中终点位置的值，由于这里的 i 和 j 从 0 开始，所以需要 -1 return dp[m - 1][n - 1]; }
2.4、不同路径 II
1、题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
示例一：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释： 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右
示例二
输入：obstacleGrid = [[0,1],[0,0]] 输出：1
2、解题思路
这道题与上一道题的解题思路相似，唯一有区别的就是，对于是障碍物的网格， 它在 dp 数组中的值为 0 ，转移方程依然与上题相同，但只有对应方格不为障碍物时， 才能将值累加到 dp[i][j] 中。
如上图所示，对于第一行中存在障碍及障碍之后的那些网格，我们需要在 dp 数组中初始化为 0 ，对于第一列的网格同理。
对于其他网格，只有当该网格上没有障碍物时，我们才去计算该网格对应的 dp 值。
当我们求一个不是障碍物网格的 dp 值时，不需要考虑它的左边和上边是否为障碍物，因为有障碍物的网格直接被初始化为 0 了。
3、解题代码
public int uniquePathsWithObstacles(int[][] obstacleGrid) { if (obstacleGrid == null || obstacleGrid.length == 0) return 0; int rowSize = obstacleGrid.length; int columnSize = obstacleGrid[0].length; int[][] dp = new int[rowSize][columnSize]; for (int i = 0;i < rowSize;i++) { for (int j = 0;j < columnSize;j++) { // 保证起点位置没有障碍物 if (i == 0 && j == 0 && obstacleGrid[i][j] == 0) { dp[i][j] = 1; } // 只有当该网格位置没有障碍物时，才进行运算 if (obstacleGrid[i][j] == 0) { // 保证当前网格的上一行（上边网格）不越界 if (i - 1 >= 0) { dp[i][j] += dp[i - 1][j]; } // 保证当前网格的前一列（左边网格）不越界 if (j - 1 >= 0) { dp[i][j] += dp[i][j - 1]; } } } } return dp[rowSize - 1][columnSize - 1]; }
2.5、整数拆分
1、题目描述
给定一个正整数 n ，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例一
输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
示例二
输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
2、解题思路
确定 dp 数组的含义，其中 dp[i] 表示划分整数 i ，可以得到的最大乘积为 dp[i]
对于一个数 i 而言，当我们对它进行第一次划分后，对 i 这个数划分的问题就变成了两个子问题的集合，我们假设它划分后的两个数分别为 i - j 和 j ，假设此时我们要划分的数为 5 ，则 我们只需要将 dp[5] 的所有划分求出来，然后再求这些划分的结果的最大值即可：
dp[5] = Math.max(dp[1] * dp[4], dp[2] * dp[3]);
1、对于一个整数 N ，它的整数划分能得到的最大乘积 dp[N] 的值为：
dp[N] = dp[i] * dp[N - i]
注意，这里的 dp[i] 和 dp[N - i] 也是划分后得到的最大乘积，也就是说，两个子问题会继续划分。
对于上面 dp[N] 的划分， dp[i] 和 dp[N - i] 既可以进行划分，同时可以不进行划分：
以 dp[5] 来说，当 i = 2 时，dp[5] = dp[2] * dp[3] ，2 如果进行划分，那么得到的值即为 1 + 1 = 2 ， 得到的值是 1 ；3 如果进行划分，那么得到的最大划分值为 1 + 2 = 3，得到的最大划分值为 2； 此时 dp[5] 的子问题在不划分时得到的乘积比划分时得到的乘积大。
状态转移方程
为什么后面的数是 j * dp[i - j] ? 这是因为由于 j 的范围是 [1, i - 1)。
dp[i] = Math.max(dp[i] , Math.max(j * (i - j) , dp[i - j] * j));
初始化 dp 数组的值
由于题目给的 n 的范围大于等于 2 ，所以我们可以算出 dp[2] = 1;dp[3] = 2;这就是 dp 数组的初始值。
3、解题代码
public int integerBreak(int n) { if (n <= 2) return 1; if (n == 3) return 2; // 初始化一个长度为 n + 1 的数组，我们最后要返回 dp[n] // 这个值表示值 n 的整数划分的最大乘积 int[] dp = new int[n + 1]; // 初始化 dp 数组 dp[2] = 1; dp[3] = 2; // 这里的 i 从 3 开始，且到 n 结束，因为我们要计算 n 的结果 for (int i = 3;i <= n;i++) { // 这里的 j 从 1 开始划分，到达 i - 1 结束 for (int j = 1;j < i - 1;j++) { dp[i] = Math.max(dp[i], Math.max((i - j) * j, j * dp[i - j])); } } return dp[n]; }
2.6、不同的二叉搜索树
1、题目描述
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？ 返回满足题意的二叉搜索树的种数。
示例一
输入：n = 3 输出：5
示例二
输入：n = 1 输出：1
2、解题思路
除了动态规划外，这道题还可以使用递归来解决，在递归时，我们的思路是这样的。
当 n == 0 时，此时只有一种结构，即空树。
当 n == 1 时，只有一种树结构；当 n == 2 时，此时有两种树结构。
当有 n 个节点时，此时我们分情况进行讨论，我们记一棵有 n 个节点的二叉树有 F(n) 种结构。
1、如果此时根节点的左子树为空，除 root 节点以外的所有节点都分布在右子树上，那么这种情况下有 F(n - 1) 种二叉树结构。
2、如果此时根节点的左子树只有一个节点，那么除 root 节点和左子树节点以外的所有节点都会分布在右子树上，这种情况下有 1 * F(n - 2) 种结构，其中 1 为左子树的情况。
3、同理，如果根节点的左子树有 a 个节点，而右子树有 n - a - 1 个节点，那么这种情况下将会有 F(a) * F(n - a - 1) 种结构。
将上面的 1，2，3 种情况加起来，就是我们最终要求的答案，接下来，我们使用动态规划来解决这道题。
明确 dp 数组的含义，dp[i] 表示有 i 个结点的二叉树结构种数，即有 i 个结点的二叉搜索树有 dp[i] 种结构。
初始化 dp 数组，当 n == 0 或 n == 1 时， dp[i] = 1。
递推公式。
我们假设左子树的结点有 j - 1 个，右子树的结点有 i - j 个，那么我们可以得到如下的递推公式。
dp[i] += dp[j - 1] * dp[i - j]
为什么使用 += ？ 这是因为 dp[i] 的值应该是左子树结点个数从 [0 , n - 1] 与右子树结点个数从 [n - 1, 0] 的乘积总和。
3、解题代码
public int numTrees(int n) { // base case ，当 n == 0 || n == 1 时，结果为 1 ，当 n == 2 时，结果为 2 if (n == 0) return 1; if (n <= 2) return n; // 创建一个 dp 数组，长度为 n + 1 ，我们要返回 dp[n] 的值 int[] dp = new int[n + 1]; // 初始化 dp 数组的值，由于我们的 i 从 1 开始，所以只需要初始化 dp[0] 即可 dp[0] = 1; // 外层循环，表示结点个数从 1 - n for (int i = 1;i <= n;i++) { // 内层循环，表示左子树结点个数从 [0, n - 1] for (int j = 1;j <= i;j++) { // 状态转移，当前 dp[i] 的值为左子树所有可能出现的情况与右子树所有可能出现情况的乘积累加 dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; }
2.7、分割等和子集
1、题目描述
给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例一
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例二
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
2、解题思路
如果数组元素的总和 sum 不是偶数，那么证明所给数组无法进行等和分割，直接返回 false。
获取数组中的最大元素 max ，如果 max > sum / 2 ，那么直接返回 false ，因为此时无法将数组分割为两个元素和相等的子集。
这道题可以转换为一种 01 背包问题，不过，与普通 01 背包问题不同的是，前者要求选取的物品的重量之和不能超过背包总容量，而这道题要求选取的数字刚好等于整个数组的元素和的一半，即 sum / 2。
dp 数组的含义。
与 01 背包问题相似，我们需要创建一个二维的 dp 数组，其中 dp[i][j] 表示从数组 nums 的下标 [0,i] 范围内选取若干个正整数（可以是 0 个），是否存在着一种选取方案使得被选取的正整数的和等于 j 。
初始时， dp 中的全部元素都为 false
dp 数组初始化
1、当要寻找的正整数的和为 0 时，那么无论此时 nums 中所给的元素下标范围如何变化，都可以找到选取方案，即 dp[i][0] 应该初始化为 true。
2、当 i 为 0 ，即 nums 数组仅有第一个元素 nums[0] 可供选择时，此时只有当 j == nums[0] 时，才有选择方案，即 dp[0][nums[0]] 应该初始化为 true。
状态转移方程，当 i > 0 且 j > 0 时，我们需要考虑以下两种情况：
如果 j >= nums[i] ，则对于当前的数字 nums[i] ，我们可以做出选择，既可以选取也可以不选取，只要两种选择有一种为 true ，那么 dp[i][j] 就为 true。
如果不选取 nums[i] ，则 dp[i][j] = dp[i - 1][j]。
如果选取 nums[i] ，则 dp[i][j] = dp[i - 1][j - nums[i]]。
如果 j < nums[i] ，则在选取的数字的和为 j 的情况下无法选取当前的数字 nums[i] ，因此有 dp[i][j] = dp[i - 1][j]。
所以我们可以得到状态转移方程如下：
if (j >= nums[i]) { // 如果要分割的数大于当前数组正在遍历的数，那么我们可以进行选择 // 只要有一个选择的结果为 true ，那么当前的 dp[i][j] 就为 true dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]; } else { // 否则无法进行选择，直接用上一次遍历的情况代替 dp[i][j] = dp[i - 1][j]; }
3、解题代码
public boolean canPartition(int[] nums) { if (nums == null || nums.length == 0) return true; int sum = 0, max = 0; for (int i = 0;i < nums.length;i++) { sum += nums[i]; // 获取数组中的最大值 max = Math.max(max, nums[i]); } // 如果 sum 不是偶数，那么直接返回 false if (sum % 2 != 0) return false; // 将 sum 除以 2 ，如果可以进行等和分割，那么数组中一定有几个元素的和等于 sum 除以 2 后的数 sum /= 2; // 如果数组中的最大值大于数组总和的一半，那么直接返回 false if (max > sum) return false; // 创建一个二维的 boolean 类型数组 dp ，这个 dp 数组有 nums.length 行 target + 1 列，其中 target = sum / 2; // dp[i][j] 表示在 nums 数组下标 [0,i] 范围内，是否可以找到一种选取方式，使得选取出来的数组值之和等于 j // 我们要求的就是 dp[nums.length - 1][target] boolean[][] dp = new boolean[nums.length][sum + 1]; // 初始化 dp 数组中的值，其中，当 j == 0 时，此时无论 nums 下标范围为多少，都可以找到一种分配方案 for (int i = 0;i < nums.length;i++) { dp[i][0] = true; } // 当 i == 0 时，dp[0][nums[0]] = true dp[0][nums[0]] = true; // 为什么外层从 1 开始？因为当 i 等于 0 时，只有 dp[0][nums[0]] 才为 true for (int i = 1;i < nums.length;i++) { int num = nums[i]; // 内层循环为何从 1 开始，从 sum 结束 // 因为当 j == 0 时，无论如何都有选取方案，这种情况我们已经在初始化过程中进行排除，所以从 1 开始 // 同时由于我们循环判断待选取的值为结果的情况，所以需要循环到 sum for (int j = 1;j <= sum;j++) { if (j >= num) { dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num]; } else { dp[i][j] = dp[i - 1][j]; } } } return dp[nums.length - 1][sum]; }
2.8、最后一块石头的重量 II
1、题目描述
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合，从中选出 任意两块石头 ，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。 那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎。
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例一：
输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
7
输入：stones = [31,26,33,21,40] 输出：5
2、解题思路
这道题和分割等和子集的思路相似，也可以转换为 01 背包问题，我们需要从数组中选择一些石头为负数，从而使得整个数组的和最小。
在数组中，我们记整个数组元素的和为 sum ，负数元素的和为 neg ，则正数元素和为sum - neg ，当 neg 与 sum - neg 最接近时，碰撞后剩下的石头最小。
也就是说， neg 越接近 sum / 2 ，碰撞后的石头越小。
所以问题转换为能否从 nums[0:i] 从取出某些石头，让这些石头的质量接近j。
确定dp 数组的含义。
和上题相似，dp[i][j] 的值表示在石头数组下标为 [0, i] 的哪些石头中，是否存在一种选取方案，使得这些石头的重量为 j。
状态转移方程和上题的一样。
dp 数组的初始化。
只有 dp[0][0] 可以初始化为 true。
3、解题代码
public int lastStoneWeightII(int[] stones) { if (stones == null || stones.length == 0) return 0; int sum = 0, size = stones.length; for (int num : stones) sum += num; int target = sum / 2; boolean[][] dp = new boolean[size + 1][target + 1]; for (int i = 0;i <= size;i++) { dp[i][0] = true; } dp[0][0] = true; for (int i = 1;i < size + 1;i++) { int curNum = stones[i - 1]; for (int j = 1;j <= target;j++) { if (j >= curNum) { dp[i][j] = dp[i - 1][j] || dp[i - 1][j - curNum]; } else { dp[i][j] = dp[i - 1][j]; } } } for (int j = target;;--j) { if (dp[size][j]) { return sum - 2 * j; } } }
2.9、最长递增子序列
1、题目描述
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例一
输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例二
输入：nums = [0,1,0,3,2,3] 输出：4
2、解题思路
使用动态规划来解决这道题，首先我们需要确定 dp 数组的含义，在这道题中 ，dp[i] 表示以数组 nums[i] 为结尾的最长递增子序列的长度。
我们可以这样思考，对于数组中的元素 nums[i] ，只要我们在[0,i - 1] 的位置中找到一个小于 nums[i] 的元素 nums[j] ，然后将 num[i] 拼接在nums[j] 后，就可以得到一个以 nums[i] 为结尾的最长递增子序列，所以我们可以得到以下的递推公式。
dp[i] = Math.max(dp[i], dp[j] + 1);// 当 nums[j] < nums[i] 且 j < i 时
初始化 dp 数组，对于数组中的每一个元素来说，其都可以单独地作为一个子序列存在，故 dp[i] = 1。
3、解题代码
public int lengthOfLIS(int[] nums) { if (nums == null || nums.length == 0) return 0; int[] dp = new int[nums.length]; // 初始化 dp ，为每个位置填充上数值 1 Arrays.fill(dp, 1); int max = Integer.MIN_VALUE; // 遍历数组，为每个数组填充合适的值 for (int i = 0;i < nums.length;i++) { // 内层循环是为外层循环服务的，目的是遍历当前数组 [0, i - 1] 的位置，然后计算出 dp[i] 的真正值 for (int j = 0;j < i;j++) { if (nums[j] < nums[i]) { // 不断更新 dp[i] 的值，如果 nums[j] < nums[i] ，那么证明找到一个以 nums[i] 为结尾的递增子序列 // 我们需要查看这个新的子序列的长度与之前找到了最长递增子序列长度的差别，然后决定是否更新最长递增子序列的值 dp[i] = Math.max(dp[i], dp[j] + 1); } } max = Math.max(max, dp[i]); } return max; }
2.10、打家劫舍
1、题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金， 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统， 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例一
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例二
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
2、解题思路
确定 dp 数组的含义。
dp[i] 表示在考虑下标 i （包括 i ）以内的房屋，最多可以偷窃的金额为 dp[i]。
确定状态转移方程。
如果选择偷取第 i 间屋子，那么我们就不能偷取第 i - 1 间屋子。
如果选择不偷取第 i 间屋子，那么此时最多能偷窃的金额即为考虑第 i - 1 间屋子时能获取的金额，即此时 dp[i] = dp[i - 1]。
我们应该在这两个选择中选取一个比较大的数，将其作为 dp[i] 的值。
dp[i] = Math.max(dp[i - 2] + value[i], dp[i - 1]);
初始化 dp 数组。
当我们只考虑第 0 间屋子时，我们能得到的最大收益是第 0 间屋子中存放的钱。
当我们只考虑第 0 间屋子与第 1 间屋子时，我们能得到的最大收益为 Math.max(value[0], value[1])。
3、解题代码
public int rob(int[] nums) { if (nums == null || nums.length == 0) return 0; // 如果长度为 1 ，那么直接返回 nums[0] 即可 if (nums.length == 1) return nums[0]; // 创建一个 dp 数组，长度为 nums.length int[] dp = new int[nums.length]; // 初始化 dp 数组 dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2;i < nums.length;i++) { // 进行状态转移，此时我们有两种选择 //1 选择不偷第 i 间房子，那么 dp[i] 的值即为 dp[i - 1] 的值 //2 选择偷第 i 间房子，那么我们就不能偷第 i - 1 间房子，此时我们在考虑第 i 间房子时最获取的最大收益即为 dp[i - 2] + 第 i 间屋子中的钱 dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); } // 返回 dp[nums.length - 1] ，这个值代表在考虑 nums.length - 1 间房子时，能获取的最大收益 return dp[nums.length - 1]; }
2.11、打家劫舍 II
1、题目描述
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。 这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例一
输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 的。
示例二
输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。
2、解题思路
这道题也是基于 打家劫舍 I 的，与打家劫舍 I 不同的是， 第一间房屋和最后一间房屋不能同时偷窃， 那么需要如何保证第一间房屋和最后一间房屋不同时偷窃呢？
1、如果我们偷窃了第 0 间房屋，那么我们就不能偷窃最后一间房屋，所以选择偷窃第 0 间房屋时，我们能偷窃的房屋下标范围为 [0, nums.length - 2] （偷窃第一间到倒数第二间房子）。
2、如果我们偷窃了最后一间房屋，那么我们就不能偷窃第一间房屋，所以选择偷窃最后一间房屋时，我们能偷窃的房屋下标范围为 [1, nums.length - 1]。
所以我们可以进行两次动态规划，动态规划的逻辑与打家劫舍 I 相同，然后取两次动态规划得到结果的最大值即可。
3、解题代码
public int rob(int[] nums) { if (nums == null || nums.length == 0) return 0; if (nums.length == 1) return nums[0]; if (nums.length == 2) return Math.max(nums[0], nums[1]); // 对 nums 中 [0, nums.length - 2] 范围的子集进行动态规划，得到结果 1 int firstResult = getMoneyByRange(nums, 0, nums.length - 2); // 对 nums 中 [1, nums.length - 1] 范围的子集进行动态规划，得到结果 2 int secondResult = getMoneyByRange(nums, 1, nums.length - 1); // 返回两个结果的最大值 return Math.max(firstResult, secondResult); } /** * 对 nums 数组中下标为 [begin, end] 范围内打家劫舍，得到利益最大值 */ private int getMoneyByRange(int[] nums, int begin, int end) { if ((end - begin + 1) == 0) return 0; if (end == begin) return nums[begin]; if (end - begin == 1) return Math.max(nums[begin], nums[end]); // 创建一个 dp 数组，长度为 nums.length int[] dp = new int[nums.length]; // 初始化 dp 数组 dp[begin] = nums[begin]; dp[begin + 1] = Math.max(nums[begin], nums[begin + 1]); for (int i = begin + 2;i <= end;i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); } return dp[end]; }
2.12、买卖股票的最佳时机
1、题目描述
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例一
输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例二
输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
2、解题思路
使用动态规划求解这道题
明确 dp 数组的含义。
对于第 i 天的用户来说，他可以持有股票，也可以不持有股票，我们 使用 0 表示这个用户持有股票，使用 1 表示这个用户未持有股票，所以这里我们需要使用一个二维的 dp 数组来进行求解，其中dp[i][j] 表示在第 i 天，用户持股状态为 j 时，所获取的最大收益 。
明确状态转移方程。
1、如果第 i 天持有股票，那么可以由两个状态推导出来。
第 i - 1 天就持有股票，那么就保持现状，所得利润就是昨天持有股票的所得利润，即此时 dp[i][0] = dp[i - 1][0]。
第 i 天买入股票，所得利润应该为负数，此时 dp[i][0] = -prices[i]。
需要在上面两个值中选择最大值，即：
dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
2、如果第 i 天没有持有股票，也可以从两个状态推导出来。
第 i - 1 天就已经不持有股票，那么保持现状，此时 dp[i][1] = dp[i - 1][1]。
第 i - 1 天持有股票，那么所得利润就是前一天持有股票时拥有的利润 dp[i - 1][0] 与今天卖出股票所得利润的总和 prices[i] ，即 dp[i][1] = dp[i - 1][0] + prices[i]。
同样需要在以上两个值中选择最大值，即：
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
初始化 dp 数组。
根据方程可知，后面 dp 数组的值都有 dp[0][0] 与 dp[0][1] 推导而来，所以我们需要初始化以上两个值，即：
dp[0][0] = -prices[0]; dp[0][1] = 0;
最终我们要返回的结果为 dp[nums.length - 1][1] ，即最后一天，用户手中没有持有股票时，能获取的最大利润。
3、解题代码
未进行空间优化前
public int maxProfit(int[] prices) { if (prices == null || prices.length < 2) return 0; // 创建一个二维的 dp 数组，其中列数为 2 ，行数为 prices.length // 其中 dp[i][0] 表示在第 i 天，用户手中持有股票时，所能获取的最大收益，dp[i][1] 表示在第 i 天，用户手中没有持有股票时，所能获取的最大收益 int[][] dp = new int[prices.length][2]; // 初始化 dp 数组，在第 0 天持有股票，那么收益为 -prices[0]，在第 0 天没有持有股票时，那么收益为 0 dp[0][0] = -prices[0]; dp[0][1] = 0; // 最终返回的结果为 dp[] for (int i = 1;i < prices.length;i++) { // 进行状态转移 //1 第 i 天手中持有股票的状态可以由两个状态得来 //1.1 第一个状态，即第 i - 1 天就已经持有股票，这种状态下则保持原样 //1.2 第二个状态，即第 i - 1 天没有持有股票，股票是在第 i 天买入的，此时应该减去价格 dp[i][0] = Math.max(dp[i - 1][0], -prices[i]); //2 同理，第 i 天手中没有持有股票的状态也由两个状态得来 //2.1 第一个状态，即第 i - 1 天就已经卖掉股票了，这种状态下保持原样 //2.2 第二个状态，即在第 i 天才卖掉股票，此时结果应该为在第 i - 1 天持有股票的利润 + 第 i 天卖出去的利润 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]); } return dp[prices.length - 1][1]; }
进行空间优化
由于第 i 天的状态只有第 i - 1 天的状态推导而来，所以我们可以缩减 dp 数组的行数，将 dp 数组改造为一个 2 * 2 的二维数组。
1、使用 dp[1][0] 表示第 i 天持有股票时获取的最大利润。
2、使用 dp[0][0] 表示第 i - 1 天持有股票时能获取的最大利润。
3、使用 dp[1][1] 表示第 i 天没有持有股票时获取的最大利润。
4、使用 dp[0][1] 表示第 i - 1 天没有持有股票时能获取的最大利润。
public int maxProfit(int[] prices) { if (prices == null || prices.length < 2) return 0; int[][] dp = new int[2][2]; dp[0][0] = -prices[0]; dp[0][1] = 0; for (int i = 1;i < prices.length;i++) { dp[1][0] = Math.max(dp[0][0], -prices[i]); dp[1][1] = Math.max(dp[0][1], dp[0][0] + prices[i]); // 更新滚动数组的值 dp[0][0] = dp[1][0]; dp[0][1] = dp[1][1]; } // 返回在最后一天没有持有股票的最大利润 return dp[1][1]; }
