Loading... # 动态规划 入门 ## 什么是动态规划 动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。 《算法图解》的定义是:“动态规划先解决子问题,再逐步解决大问题” ## 背包问题 假设你是一个贪婪的小偷,背着可装35磅物品的背包,在商场伺机偷取物品,你可盗窃的物品有下面三种: | 物品 | 价格 | 重量 | | ----|---- | ---- | | 音响 | 3000美元 | 30磅| | 笔记本电脑 | 2000美元 | 20磅| | 吉他 | 1500美元 | 15磅 | ### 简单算法 最简单的算法是:枚举出所有可能的组合,从中找出价值最高的组合 这样可行,但速度非常慢。在仅有三件商品的情况下,需要计算8个不同的集合;有四件商品需要计算16个集合。每增加一件商品,需要计算的集合数都将翻倍!这种算法的运行时间为 $$ O(a^n) $$ 。 ### 动态规划 动态规划的核心思想就是拆分子问题,记住过往,减少重复计算。 并且动态规划一般都是自底向上的。 《算法图解》并没有讲清楚何为动态规划,以及其实现,我将结合[这篇博客](https://cloud.tencent.com/developer/article/1817113)来讲解 总的来说有四步: - 穷举分析 - 确定边界 - 找出规律,确定最优子结构 - 写出状态转移方程 什么是最优子结构?有这么一个解释: ```一道动态规划问题,其实就是一个递推问题。假设当前决策结果是f(n),则最优子结构就是要让 f(n-k) 最优,最优子结构性质就是能让转移到n的状态是最优的,并且与后面的决策没有关系,即让后面的决策安心地使用前面的局部最优解的一种性质``` **1. 穷举分析** 背包可放35磅 放15磅 | 物品\重量 | 15 | | :-: | :-: | |吉他 15磅|1500| |笔记本电脑 20磅|1500| |音响 30磅|1500| 放20磅 | 物品\背包价值\重量 | 15 | 20 | | :-: | :-: | :-: | |吉他 15磅 1500美元|1500|1500| |笔记本电脑 20磅 2000美元|1500|2000| |音响 30磅 3000美元|1500|2000| 放35磅 | 物品\背包价值\重量 | 15 | 20 | 35 | | :-: | :-: | :-: | :-: | |吉他 15磅 1500美元|1500|1500|1500| |笔记本电脑 20磅 2000美元|1500|2000|3500| |音响 30磅 3000美元|1500|2000|3500| 不难看出: 1.如果放不下当前行的物品,则直接从上方单元格抄下价格 2.如果放得下,判断本行与上方的价值,填入最高价值 **2.确定边界** 边界情形为第一行,即最轻的物品需要填入,以保证下方单元格能获取到价格 **3.确定最优子结构** 当前单元格 = Max(上方单元格价值, 本行物品加入后的价值) 将第 i 件物品的价值 **W[i\]** 加上 <ins>向容量为v-C[i] 的背包装入前 i-1 件物品</ins> (现有容量v - 当前物品大小C[i]) 这个 **子问题** 的最大价值 **F[i-1\][v-C[i\]]** (先把第 i 件物品加入背包,然后考虑安排剩余的空间容量) **4.状态转移方程** f[i\][j] = Max( f[i - 1\][j] , f[i-1\][v-C[i]]) ## leetcode例题 [5.最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring) 给你一个字符串 s,找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。 示例 1: ``` 输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。 ``` 示例 2: ``` 输入:s = "cbbd" 输出:"bb" ``` 提示: `1 <= s.length <= 1000` `s` 仅由数字和英文字母组成 代码实现: ```java public static String longestPalindrome(String s) { int len = s.length(); if (len == 1) { return s; } int rsLen = 1; int start = 0; // 创建表格 boolean[][] dp = new boolean[len][len]; for (int i = 0; i < len; i++) { dp[i][i] = true; } char[] arr = s.toCharArray(); /* 初始化后的示例 0 1 2 3 4 right 0 T F F F F 1 F T F F F 2 F F T F F 3 F F F T F 4 F F F F T left 对角线 单字符是回文串 */ // 先按 右指针(列) 遍历 for (int right = 1; right < len; right++) { // 再按行遍历 // 只需判断对角线上部,即 left < right for (int left = 0; left < right; left++) { // 判断两端字符相等 if (arr[left] == arr[right]) { // 边界情形 字符串长度小于3的情况 if (right - left < 3) { dp[left][right] = true; } else { // 普通情况,两头的字符相等的话,找 left + 1, right - 1 // 即指针都向中间移一格,如果中间的是回文,那当前也是回文 dp[left][right] = dp[left + 1][right - 1]; } } // 如果当前是回文,且当前字符串长度大于最大字符串长度 if (dp[left][right] && right - left + 1 > rsLen) { start = left; // 最大字符串长度 // 如果直接取右指针会遇到奇偶问题 rsLen = right - left + 1; } } } return s.substring(start, start + rsLen); } ``` </br> 参考: 1.《算法图解》人民邮电出版社 2. [看一遍就理解:动态规划详解](https://cloud.tencent.com/developer/article/1817113) 最后修改:2022 年 12 月 20 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 1 本作品采用 CC BY-NC-SA 4.0 International License 进行许可。