在哪家网站做外贸比较好,代做淘宝网站,网站优化合同,上海免费网站建站模板在前面的动态规划系列文章中#xff0c;关于如何对递归进行分析的四种基本模型都介绍完了#xff0c;再来回顾一下#xff1a;
从左到右模型 #xff1a;arr[index ...] 从 index 之前的不用考虑#xff0c;只考虑后面的该如何选择 。范围尝试模型 #xff1a;思考 [L ,…在前面的动态规划系列文章中关于如何对递归进行分析的四种基本模型都介绍完了再来回顾一下
从左到右模型 arr[index ...] 从 index 之前的不用考虑只考虑后面的该如何选择 。范围尝试模型 思考 [L ,R] 两端即 开头和结尾 处分别该如何取舍。样本对应模型 以 结尾位置 为出发点思考两个样本的结尾都会产生哪些可能性 。业务限制模型 不能够明确的知道一个参数的变化范围通过业务的限制找到 最差情况 进行估计。
接下来的几篇文章我们继续深挖动态规划的一些 优化策略。
通过前面文章的学习相信小伙伴都能够根据不同模型的套路熟练的改出 严格表依赖 的动态规划版本了。
但有个问题
记忆化搜索 和 严格 dp 表依赖 的时间复杂度一样记忆化搜索的代码写起来容易为什么还非要找到动态规划的 状态转移方程 进而修改成为严格表依赖关系的呢。接下来我们通过一道题目 揭晓答案
找零钱问题Ⅰ
给定一个面值数组 arr 其中的值均为无重复的正数每一个值代表一种面值张数无限。求能够组成 aim 的方法数是多少。 示例 1 输入: arr {1, 2} aim 4 。 输出 3 解释 共三种组合方式 1 1 1 1 41 1 2 42 2 4 示例 2 输入: arr {1, 2, 5} aim 6 。 输出 5 解释 共五种组合方式 1 1 1 1 1 1 61 1 1 1 2 61 1 2 2 62 2 2 61 5 6 首先我们依然采用最朴素的 暴力递归 来思考这道题目。
思路
这道题就是典型的 从左到右模型 因此递归就可以按照 在 arr[index ...]数组中index 之前的不用考虑只考虑后面的该如何选择 的思路来划分情况
当前 index 下标对应的面值 参与 组合选择任意张数之后能有多少种情况当前 index 下标对应的面值 不参与 组合选择任意张数之后能有多少种情况。
因为要求总的情况因此要返回这两种情况的 总和 。
代码
public static int coinsWay(int[] arr, int aim) {if (arr null || arr.length 0 || aim 0) {return 0;}return process(arr, 0, aim);
}public static int process(int[] arr, int index, int rest) {if (index arr.length) { return rest 0 ? 1 : 0;}int ways 0;for (int zhang 0; zhang * arr[index] rest; zhang) {ways process(arr, index 1, rest - (zhang * arr[index]));}return ways;
}代码解释
递归中base case 为下标来到最后时如果剩余的钱数为 0 说明前面的组合刚好能够凑出 aim 值记为有效的一种情况。
选和不选 体现在 zhang 从 0 开始直到该张数的面值超过了剩余钱数 rest 为止。继续调用递归且下标 index 1 剩余钱数也相应减少。最终返回总的方法数即可。 写出该暴力版的递归之后修改出动态规划版的就很容易了。
动态规划版
public static int dp(int[] arr, int aim) {if (arr null || arr.length 0 || aim 0) {return 0;}int N arr.length;int[][] dp new int[N 1][aim 1];dp[N][0] 1;for (int index N - 1; index 0; index--) {for (int rest 0; rest aim; rest) {int ways 0;for (int zhang 0; zhang * arr[index] rest; zhang) {ways dp[index 1][rest - (zhang * arr[index])];}dp[index][rest] ways;}}return dp[0][aim];
}代码解释
可变的参数有两个总的面值个数 N 和 剩余的目标钱数 rest 。因此需要设置一个二维的 dp 表数组由于 N, rest 的取值范围是 0~N 、0~aim 因此数组大小设置为 dp[N 1][aim 1] 。
递归代码 index arr.length 可知初始只有 dp[N][0] 的值为 1 。
因为递归中只依赖 index 1 的值所以 dp 表倒着填写。
根据递归调用 process(arr, 0, aim) 可知最终返回 dp[0][aim] 。 之前的文章写到这里就结束了但 这次不一样
观察递归的代码发现竟然有 3 层 for 循环。为什么呢
思考后发现 dp 表中的每个位置同样需要 枚举 后才能知道之前的题目能够直接计算出来。那有没有办法消掉这层枚举的 for 循环呢答案是有的
下面我们通过画 dp 表探寻该动态规划应如何进一步优化。 假设此时剩余的总钱数 rest 10面值数 arr[i] 3 。 一图胜千言~
通过枚举代码可知arr[i][10] 的值红色 黄色 3 个紫色。 黄色不选面值为 3 的钱币时rest 仍为 10依赖下一格 i 1。 紫色分别选 1 张、2 张、3张…时rest 对应每次减 3 且依赖下一格 i 1 行。 稍加思考发现蓝色的位置即 arr[i][10 - 3] 位置的值正是 3 个紫色的总和。那么就可以将 红色 黄色 3 个紫色改为 红色 黄色 蓝色这样就不需要一直往前寻找了减少一个 for 循环。
最终优化版动态规划
public static int dp(int[] arr, int aim) {if (arr null || arr.length 0 || aim 0) {return 0;}int N arr.length;int[][] dp new int[N 1][aim 1];dp[N][0] 1;for (int index N - 1; index 0; index--) {for (int rest 0; rest aim; rest) {// 先令 红色 等于 黄色部分dp[index][rest] dp[index 1][rest];// 如果没越界说明前面有蓝色部分再加上蓝色部分if (rest - arr[index] 0) {dp[index][rest] dp[index][rest - arr[index]];}}}return dp[0][aim];
}注意看越界的判断哦黄色和蓝色分开加。这样就完成了最终版的动态规划~
回答最初的问题为什么有了记忆化搜索还要写出严格的表依赖呢
为了避免枚举行为多产生的 for 循环有了 表依赖 才能找到如何 优化枚举
因此前面学习的如何一步步的将暴力递归修改为严格表依赖动态规划的基础要打牢哦还不会的赶快关注一下回顾前面的几篇文章吧
~ 点赞 ~ 关注 ~ 不迷路 ~
------------- 往期回顾 ------------- 【算法 - 动态规划】原来写出动态规划如此简单 【算法 - 动态规划】最长公共子序列问题 【算法 - 动态规划】最长回文子序列 【算法 - 动态规划】力扣 691. 贴纸拼词 【算法 - 动态规划】京东面试题 - 洗咖啡杯问题 【堆 - 专题】“加强堆” 解决 TopK 问题 AC 此题链表无敌
