动态规划 入门
动态规划 入门
什么是动态规划
动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题[1]和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
《算法图解》的定义是：“动态规划先解决子问题，再逐步解决大问题”
背包问题
假设你是一个贪婪的小偷，背着可装35磅物品的背包，在商场伺机偷取物品，你可盗窃的物品有下面三种：
物品 | 价格 | 重量 |
|---|---|---|
音响 | 3000美元 | 30磅 |
笔记本电脑 | 2000美元 | 20磅 |
吉他 | 1500美元 | 15磅 |
简单算法
最简单的算法是：枚举出所有可能的组合，从中找出价值最高的组合 这样可行，但速度非常慢。在仅有三件商品的情况下，需要计算8个不同的集合；有四件商品需要计算16个集合。每增加一件商品，需要计算的集合数都将翻倍！这种算法的运行时间为
O(an)
。
动态规划
动态规划的核心思想就是拆分子问题，记住过往，减少重复计算。 并且动态规划一般都是自底向上的。 《算法图解》并没有讲清楚何为动态规划，以及其实现，我将结合这篇博客来讲解 总的来说有四步：
- 穷举分析
- 确定边界
- 找出规律，确定最优子结构
- 写出状态转移方程
什么是最优子结构？有这么一个解释：
一道动态规划问题，其实就是一个递推问题。假设当前决策结果是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] 加上 向容量为v-C[i] 的背包装入前 i-1 件物品 (现有容量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.最长回文子串 给你一个字符串 s，找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd"
输出："bb"提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
代码实现：
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);
}参考： 1.《算法图解》人民邮电出版社 2. 看一遍就理解：动态规划详解
腾讯云开发者
