# 动态规划
# 什么是动态规划？
动态规划(英文：Dynamic programming，简称 DP)，是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的字问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
# 动态规划核心思想
动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。
举一个例子：
A ： "1+1+1+1+1+1+1+1 = ？"
A ： "上面等式的值是多少"
B ： 计算 "8"
A : 在上面等式的左边写上 "1+" 呢？
A : "此时等式的值为多少"
B : 很快得出答案 "9"
A : "你怎么这么快就知道答案了"
A : "只要在8的基础上加1就行了"
A : "所以你不用重新计算，因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"
# 青蛙跳阶问题
leetcode原题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个10级的台阶总共有多少总跳法。
第一次见这个题的时候，可能有点蒙圈，但是可以思考一下：
- 想跳到第10级台阶，要么是先跳到第9级，要么是先跳到第8级。
- 同理，要想跳到第9级，要么是先跳到第8级，要么是先跳到第7级。
- ....
假设跳到第n级台阶的跳数，我们定义为f(n)，很显然可以得出以下公式：
f(10) = f(9) + f(8)
f(9) = f(8) + f(7)
...
f(3) = f(2) + f(1)
即通用公式为：f(n) = f(n-1) + f(n-2)
那f(2)和f(1)等于多少呢？
- 当只有2级台阶时，只有两种跳法，第一种是跳2级，第二种是跳1级再跳1级。即f(2) = 2
- 当只有1级台阶时，只有一种跳法。即f(1) = 1
# 暴力递归
因此可以通过递归解决这个问题：
function numWays(n) {
if (n <= 2) {
return n;
}
return numWays(n - 1) + numWays(n - 2);
}
这个方法虽然可以得到正确答案，但是解法中存在大量的重复计算，所以我们可以把计算好的答案存储下来，进行性能优化。
# 备忘录递归
一般使用一个数组和一个哈希map来充当备忘录，把每次计算的结果都记录下来，避免重复运算。
let tempMap = {};
function numWays(n) {
if (n === 0) {
return 1;
}
if (n <= 2) {
return n;
}
// 先判断备忘录中是否存在要计算的值
if (tempMap[n]) {
return tempMap[n];
} else {
tempMap[n] = numWays(n - 1) + numWays(n - 2);
return tempMap[n];
}
}
# 动态规划
动态规划跟备忘录递归的解法思想是一致的，都是减少重复计算，时间复杂度也差不多。
- 备忘录递归，是从f(10)往f(1)方式从顶到底延伸求解到。
- 动态规划从较小问题的解，由交叠性质，逐步决策出较大问题的解，它是从f(1)到f(10)从底到顶求解。
动态规划有几个典型特征：最优子结构、状态转移方程、边界、重叠子问题。在青蛙跳阶问题中：
- f(n-1)和f(n-2)称为f(n)的最优子结构
- f(n)=f(n-1)+f(n-2)称为状态转移方程
- f(1)=1，f(2)=2就是边界
- f(10)=f(9)+f(8)，f(9)=f(8)+f(7)就是重叠子问题
function numWays(n) {
if (n <= 2) {
return n;
}
let a = 1;
let b = 2;
let temp = 0;
for (let i = 3; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return temp;
}
动态规划的空间复杂度，只需要O(1)而备忘录需要O(n)。
# 最长回文子串
leetcode原题：给你一个字符串，找到字符串中最长的回文子串
# 暴力解法
const isPalidrome = (s, left, right) => {
while(left < right) {
if (s[left] !== s[right]) {
return false;
}
left++;
right--;
}
return true;
};
const longestPalindrome = function(s,) {
const len = s.length;
if (len < 2) {
return s;
}
let maxLen = 1;
let begin = 0;
for (let i = 0; i < len - 1; i++) {
for (let j = i + 1; j < len; j++)
if (j - i + 1 > maxLen && isPalidrome(s, i, j)) {
maxLen = j - i + 1;
begin = i;
}
}
return s.slice(begin, begin + maxLen);
};
# 动态规划
思路如下：
- 对于一个子串而言，如果它是回文串并且长度大于2，那么将其首尾两个字符串去除后，它仍然是回文串。
- 状态
dp[i][j]表示子串s[i...j]是否为回文子串 - 状态转移方程
dp[i][j] = (s[i] === s[j]) && dp[i + 1][j - 1] - 边界：j - 1 - (i + 1) + 1 < 2，整理得j - i < 3
const longestPalindrome = function(s) {
const len = s.length;
if (len < 2) {
return s;
}
let maxLen = 1;
let begin = 0;
let dp = new Array(len).fill([]).map(() => Array(len).fill(false));
// 初始化：所有长度为1的子串都是回文串
for (let i = 0; i < len; i++) {
dp[i][i] = true;
}
// 先枚举子串长度
for (let l = 2; l <= len; l++) {
// 枚举左边界
for(let i = 0; i < len; i++) {
// 由l和i可以确定右边界
let j = l + i - 1;
// 如果右边界越界，则退出当前循环
if (j >= len) {
break;
}
if (s[i] !== s[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
};
# 动态规划的解题套路
动态规划的核心思想就是拆分子问题，记住过往，减少重复计算。并且动态规划一般都是自底向上的，因此到这里，基于青蛙跳阶问题，总结一下动态规划的思路：
- 穷举分析
- 确定边界
- 找出规律，确认最优子结构
- 写出状态转移方程
# 穷举分析
- 当台阶数是1的时候，有一种跳法，
f(1)=1 - 当只有2级台阶时，有两种跳法，第一种是直接跳两级，第二种是先跳一级，然后再跳一级。
- ...
# 确定边界
通过穷举分析，我们发现，当台阶数是1的时候或者2的时候，可以明确知道青蛙跳法。f(1) = 1，f(2) = 2，当台阶n>=3时，已经呈现出规律f(3)=f(2)+f(1)，因此f(1) = 1，f(2) = 2就是青蛙跳阶的边界。
# 找规律，确定最优子结构
n>=3时，已经呈现出规律f(n)=f(n-1)+f(n-2)，因此f(n-1)和f(n-2)称为f(n)的最优子结构。什么是最优子结构？有这么一个解释：
一道动态规划问题，其实就是一个递推问题。假设当前决策结果是f(n)，则最优子结构就是要让f(n-k)最优，最优子结构性质就是能让转移到n的状态是最优的，并且与后面的决策没有关系，即让后面的决策安心地使用前面的局部最优解的一种性质
# 写出状态转移方程
通过前面3步，穷举分析、确定边界、最优子结构，我们就可以得出状态转移方程：f(n)=f(n-1) +f(n-2)。
# 最长严格递增子序列
leetcode原题：给你一个整数数组nums，找到其中最长严格递增子序列的长度。
示例1:
输入: nums = [10, 9i, 2, 5, 3, 7, 101, 18]
输出: 4
解释：最长递增子序列是[2, 3, 7, 101]，因此长度为4
我们按照以上动态规划的解题思路
- 穷举分析
- 确定边界
- 找规律，确定最优子结构
- 状态转移方程
← 牛顿迭代法