day6_动态规划1

本文主要是介绍day6_动态规划1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划

一、动态规划解题套路框架

动态规划问题性质

1.暴力递归

引出 重叠子问题

2.使用“备忘录”

目的：重叠子问题(使用数组或哈希表)

带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和常见的动态规划解法已经差不多了，只不过这种解法是「自顶向下」进行「递归」求解，我们更常见的动态规划代码是「自底向上」进行「递推」求解。

3.自底向上

啥叫「自底向上」？反过来，我们直接从最底下、最简单、问题规模最小、已知结果的 f(1) 和 f(2)（base case）开始往上推，直到推到我们想要的答案 f(20)。这就是「递推」的思路，这也是动态规划一般都脱离了递归，而是由循环迭代完成计算的原因。

4.状态转移方程

f(n) 的函数参数会不断变化，所以你把参数 n 想做一个状态，这个状态 n 是由状态 n - 1 和状态 n - 2 转移（相加）而来，这就叫状态转移，仅此而已。

状态转移方程直接代表着暴力解法。

千万不要看不起暴力解，动态规划问题最困难的就是写出这个暴力解，即状态转移方程。

只要写出暴力解，优化方法无非是用备忘录或者 DP table，再无奥妙可言。

5.细节优化：

一般是动态规划问题的最后一步优化，如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试缩小 DP table 的大小，只记录必要的数据，从而降低空间复杂度

例题1，零钱兑换

带备忘录的递归解法

class Solution {int[] memo;int coinChange(int[] coins, int amount) {memo = new int[amount + 1];// 备忘录初始化为一个不会被取到的特殊值，代表还未被计算Arrays.fill(memo, -666);return dp(coins, amount);}int dp(int[] coins, int amount) {if (amount == 0) return 0;if (amount < 0) return -1;// 查备忘录，防止重复计算if (memo[amount] != -666)return memo[amount];int res = Integer.MAX_VALUE;for (int coin : coins) {// 计算子问题的结果int subProblem = dp(coins, amount - coin);// 子问题无解则跳过if (subProblem == -1) continue;// 在子问题中选择最优解，然后加一res = Math.min(res, subProblem + 1);}// 把计算结果存入备忘录memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;return memo[amount];}
}

动态规划解法

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];// 数组大小为 amount + 1，初始值也为 amount + 1Arrays.fill(dp, amount + 1);// base casedp[0] = 0;// 外层 for 循环在遍历所有状态的所有取值for (int i = 0; i < dp.length; i++) {// 内层 for 循环在求所有选择的最小值for (int coin : coins) {// 子问题无解，跳过if (i - coin < 0) {continue;}dp[i] = Math.min(dp[i], 1 + dp[i - coin]);}}return (dp[amount] == amount + 1) ? -1 : dp[amount];}
}

总结

计算机解决问题其实没有任何特殊的技巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。

列出状态转移方程，就是在解决“如何穷举”的问题。之所以说它难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不那么容易穷举完整。

备忘录、DP table 就是在追求“如何聪明地穷举”。用空间换时间的思路，是降低时间复杂度的不二法门，除此之外，试问，还能玩出啥花活？

一、动态规划设计：最长递增子序列

参考链接动态规划设计：最长递增子序列 | labuladong 的算法笔记

设计状态转移方程

借助经典的「最长递增子序列问题」来讲一讲设计动态规划的通用技巧：数学归纳思想

1.最长递增子序列问题（动态规划）

int lengthOfLIS(int[] nums) {// 定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度int[] dp = new int[nums.length];// base case：dp 数组全都初始化为 1Arrays.fill(dp, 1);for (int i = 0; i < nums.length; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);}}int res = 0;for (int i = 0; i < dp.length; i++) {res = Math.max(res, dp[i]);}return res;
}

2.最长递增子序列问题(动态规划+二分查找)

int lengthOfLIS(int[] nums) {int[] top = new int[nums.length];// 牌堆数初始化为 0int piles = 0;for (int i = 0; i < nums.length; i++) {// 要处理的扑克牌int poker = nums[i];/***** 搜索左侧边界的二分查找 *****/int left = 0, right = piles;while (left < right) {int mid = (left + right) / 2;if (top[mid] > poker) {right = mid;} else if (top[mid] < poker) {left = mid + 1;} else {right = mid;}}/*********************************/// 没找到合适的牌堆，新建一堆if (left == piles) piles++;// 把这张牌放到牌堆顶top[left] = poker;}// 牌堆数就是 LIS 长度return piles;
}

3. 354.俄罗斯套娃信封问题(hard)

//在二分查找的基础上解决，只使用动态规划会超出时间限制

1. 将宽度升序排序，在宽度相同的基础上进行降序排序

   因为宽度或高度有一个相同就不能嵌套，所以，为了保证结果不会出现两个宽度相同的信封而将高度降序

2. 只根据处理后的高度进行最长递增子序列问题解决

class Solution {
// envelopes = [[w, h], [w, h]...]
public int maxEnvelopes(int[][] envelopes) {int n = envelopes.length;// 按宽度升序排列，如果宽度一样，则按高度降序排列Arrays.sort(envelopes, (int[] a, int[] b) -> {return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];});// 对高度数组寻找 LISint[] height = new int[n];for (int i = 0; i < n; i++)height[i] = envelopes[i][1];return lengthOfLIS(height);
}int lengthOfLIS(int[] nums) {int[] top = new int[nums.length];// 牌堆数初始化为 0int piles = 0;for (int i = 0; i < nums.length; i++) {// 要处理的扑克牌int poker = nums[i];/***** 搜索左侧边界的二分查找 *****/int left = 0, right = piles;while (left < right) {int mid = (left + right) / 2;if (top[mid] > poker) {right = mid;} else if (top[mid] < poker) {left = mid + 1;} else {right = mid;}}/*********************************/// 没找到合适的牌堆，新建一堆if (left == piles) piles++;// 把这张牌放到牌堆顶top[left] = poker;}// 牌堆数就是 LIS 长度return piles;
}}

二、最优子结构原理和dp数组遍历方向

重点

1、到底什么才叫「最优子结构」，和动态规划什么关系。

子问题之间独立，最优子结构性质作为动态规划问题的必要条件，一定是让你求最值的

动态规划不就是从最简单的 base case 往后推导吗，可以想象成一个链式反应，以小博大。但只有符合最优子结构的问题，才有发生这种链式反应的性质。

2、如何判断一个问题是动态规划问题，即如何看出是否存在重叠子问题。

求最值，抽象出递归框架，如果达到某个状态可以由不同的子状态组成，那么这个问题就存在重叠子问题

3、为什么经常看到将 dp 数组的大小设置为 n + 1 而不是 n。

因为递归一般是使用方法，而dp一般使用数组结合for循环进行计算无法定义 base case

1. dp 函数的定义，dp(s1, i, s2, j) 计算 s1[0..i] 和 s2[0..j] 的编辑距离，那么 i, j 等于 -1 时代表空串的 base case，所以函数开头处理了这两种特殊情况。
2. 再看 dp 数组，你当然也可以定义 dp[i][j] 存储 s1[0..i] 和 s2[0..j] 的编辑距离，但问题是 base case 怎么搞？索引怎么能是 -1 呢？
3. 所以我们把 dp 数组初始化为 int[m+1][n+1]，让索引整体偏移一位，把索引 0 留出来作为 base case 表示空串，然后定义 dp[i+1][j+1] 存储 s1[0..i] 和 s2[0..j] 的编辑距离

4、为什么动态规划遍历 dp 数组的方式五花八门，有的正着遍历，有的倒着遍历，有的斜着遍历。

重点掌握两点：

1、遍历的过程中，所需的状态必须是已经计算出来的。

2、遍历结束后，存储结果的那个位置必须已经被计算出来。

这篇关于day6_动态规划1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---