# 动态规划
动态规划（Dynamic Programming，DP）一般用于可以通过子问题来寻找最终答案的题目，当然所有子问题及子问题的解法是一样。这类题目的关键词：重叠子问题，最优子结构
复杂度：动态规则的时间复杂度 = 递归函数的复杂度 * 递归函数的调用次数
# 粟子
动态规则常用于解决路径及回文串等相关的题目中
# 斐波那契数列 (opens new window)
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1
暴力递归法
var fib = function(n) {
if(n<2) return n
return fib(n-1)+fib(n-2)
};
时间复杂度：O(2^n) * O(1) = O(2^n)
问题：在递归调用的时候会造成重复的计算，比如：fib(7) = fib(6) + fib(5)、fib(6) = fib(5)+fib(4),这里 fib(5) 就重复计算了
优化一：缓存
添加一个对象将已经计算过的值缓存起来
/**
* @param {number} n
* @return {number}
*/
let map = []
var fib = function(n) {
if(n<2) return n
if(map[n]) return map[n]
map[n] = fib(n-1)+fib(n-2)
return map[n]%1000000007
};
优化后所有的值只需调用一次就可以了，所以递归的调用次数为 n 次。那么得到时间复杂度：O(n) * O(1) = O(n)
但是额外创建了 map 存储所有值，所以额外添加了空间复杂度：O(n)，典型的空间换时间
至底向上解决
上面的例子都是至顶向下的解法，现在使用迭代的方式完成致底向上的解法
/**
* @param {number} n
* @return {number}
*/
var fib = function(n) {
let map = []
map[0] = 0
map[1] = 1
for(let i = 2; i<=n; i++){
map[i] = (map[i-1]+map[i-2])%1000000007
}
return map[n]
};
时间复杂度：O(n)
空间复杂度：O(n)
优化二：优化空间复杂度
根据斐波那契的规律，F(N) = F(N - 1) + F(N - 2)，实际上并不需要保存所有的值，只需要保存 F(N - 1) 和 F(N - 2) 这两个值即可，所以在至底向上的解法上可以做进一步优化
/**
* @param {number} n
* @return {number}
*/
var fib = function(n) {
if(n<2) return n
let a = 0
let b = 1
let result = 0
for(let i = 2; i<=n; i++){
result = (a+b) %1000000007
a = b
b = result
}
return result
};
只需要额外三个变量就可以完成优化，空间复杂直接降到 O(1)
# 爬楼梯 (opens new window)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
- 示例一. 爬2个台阶，有两种解法：
1. 1阶 + 1阶
2. 2阶
- 示例二. 爬3个台阶，有三种解法：
1. 1阶 + 1 阶 + 1 阶
2. 1阶 + 2 阶
3. 2阶 + 1 阶
思路：
因为每次可以选择走一步或两步，所以到达
n阶的方式有两种：从n-1阶走一步到达n阶，也可以从n-2阶走两步到达n阶，所以走n创的可能性为f(n) = f(n-1)+f(n-2)n-1和n-2的可能走法也是同理，直接到走1阶或2阶为止所以计算思路就是从
1阶开始计算一直迭代到n阶就得到走n的所有走法
问题的规模随着拆分，会变得越来越小，这种将问题拆解，并通过计算小问题的解，最终计算出最优解的思想就是动态规划
let allMethods = function(n){
let dp = []
dp[0] =1;
dp[1] = 1;
for( let i = 2 ; i <= n; i ++ ){
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
此算法的时间复杂度为O(n)，空间复杂度为：O(n)
此题跟斐波那契数列的解法几乎一致
# 322. 零钱兑换 (opens new window)
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。
你可以认为每种硬币的数量是无限的。
示例：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
示例 4：
输入：coins = [1], amount = 1
输出：1
示例 5：
输入：coins = [1], amount = 2
输出：2
解题思路
对于总金额 amount 假设有零钱 n，那么 amount的最少零钱数为 dp[amount-n]+1，dp 存储的是所有金额的最少硬币数，amount-n 必然是小于 amount的，所以跟爬楼梯一样，我们要得到总金额 amount 的最少硬币数，先从金额为 1 开始得到每个金额的最少硬币数直接 n 为止
使用动态规划迭代至底向上解法
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function(coins, amount) {
// amount是最后的长度下标，那么这个数据长度应回 amount+1
// 因为是以最小为最优解，所以默认给所有 dp 赋最大值
let dp = (new Array(amount+1)).fill(Infinity)
dp[0] = 0
for(let i = 0;i<dp.length;i++){
for(let j of coins){
if(i - j < 0) continue // 如果这个零食比总金额大，则路过
dp[i] = Math.min(dp[i], 1 + dp[i-j]) // 取最优解
}
}
return dp[amount] === Infinity ? -1 : dp[amount]
};
暴力递归
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function(coins, amount) {
let result = Infinity
if(amount === 0){
return 0
}
if(amount < 0){
return -1
}
for(let i of coins){
let subResult = coinChange(coins, amount - i)
if(subResult === -1) continue
result = Math.min(result, subResult+1)
}
return result === Infinity ? -1 : result
};
时间复杂度分析：递归总数 x 每个递归函数的时间
递归总数：递归树节点个数，是 O(n^k)
每个递归函数的时间：每个递归函数中含有一个
for循环,O(k)
所以总时间复杂度为 O(k * n^k)，指数级别
执行上述的代码将会提示运行超时，可以参考之前斐波那契数的题目做优化
优化一：缓存
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
let map = []
var coinChange = function(coins, amount) {
let result = Infinity
if(amount === 0){
return 0
}
if(amount < 0){
return -1
}
if(map[amount] !== undefined){
return map[amount]
}
for(let i of coins){
let subResult = coinChange(coins, amount - i)
if(subResult === -1) continue
result = Math.min(result, subResult+1)
}
map[amount] = (result === Infinity ? -1 : result)
return map[amount]
};
时间复杂度：递归数量（n），每个递归需要的时间仍是（k），所以最终的复杂度为 O(kn)
# 343. 整数拆分 (opens new window)
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
思路
乍一看跟上面的零钱兑换非常的相似，所以思路也是一样的从 1 开始迭代得到最优的值，直到 n；
对于每个当前整数 n，再从 1到n 进行拆分，然后取他们之中的最大值
如例子 4 ，如果只是拆成两个数时，可拆的可能性为
- 1*3 = 3
- 2*2 = 4
- 3*1 = 3
但是题目描述的是至少拆成两个以上的数，所以对于上面 1*3 这种情况，1 是不可能再拆了，但 3 还可以，所以还需要考虑将 3 进行拆后的情况，以此类推所以的可能拆分情况为：
- 1*3 = 3
- 1*1*2 = 2
- 1*1*1*1*1 = 1
- 2*2 = 4
- 2*1*1 = 2
- 3*1 = 3
所以 dp[4] = 4. 上面例子可以看到出现了冗余，先不做处理
然后将这一小段转换成代码为：
// i 表示当前要拆的整数
// 这段代码只考虑拆成两个的情况下
let max = 0
for(let j = 1; j<i; j++){
max = Math.max(max, j*(i-j))
}
// 拆出来的数继续拆的情况
let max = 0
for(let j = 1; j<i; j++){
max = Math.max(max, j*(i-j), j*dp[i-j]) // 继续拆后的值可以直接从 dp 中取
}
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function(n) {
let dp = []
for(let i = 1; i<=n; i++){
let max = 0
for(let j = 1; j<i; j++){
max = Math.max(max, j*(i-j), j*dp[i-j])
}
dp[i] = max
}
return dp[n]
};
# 1143. 最长公共子序列 (opens new window)
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
思路
粟子 text1 = "abcde", text2 = "ace"，假设 dp[i][j] 表示text1[i] 到 text2[j] 之间的最多公共子序列个数
那么计算 dp[i][j] 的最长子序列的方式有几种情况：
s[i]===s[j]，那么dp[i][j] = dp[i-1][j-1]+1。 如dp[2][1]表示abc和ac之间最长公共个数，此时text1[2] === text2[1]，所以要先知道dp[1][0]的最长公共子序列，再此基本上+1s[i]!==s[j], 如dp[2][2]表示abc和ace之间最长公共个数，此时text1[2] !== text2[2]，要么它的最长公共子序列就等之前的最长的公共子序列，接近dp[2][2]范围的区间有dp[2][1]和dp[1][2]，取他们的最大值
/**
* @param {string} text1
* @param {string} text2
* @return {number}
*/
var longestCommonSubsequence = function(text1, text2) {
let dp = new Array(text1.length).fill('').map(() => new Array(text2.length))
for(let i = 0; i<text1.length; i++){
for(let j=0; j<text2.length;j++){
if(text1[i] === text2[j]){
dp[i][j] = ((dp[i-1]||[])[j-1]||0)+1
} else {
dp[i][j] = Math.max(dp[i][j-1]||0, (dp[i-1]||[])[j]||0)
}
}
}
return dp[text1.length-1][text2.length-1]
};
# 最长递增子序列 (opens new window)
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
思路：
定义
dp存储组数每个值的最长递增子序列的个数那么可以得到公式
dp[n] = dp[n] > dp[n-m] ? dp[n-m] +1: dp[n-m]假设当前数组
data已经得到dp = [1,2,4,2]，那么如果需要得到dp[4]的最优解，则需要将下标为data[4]的值与之前的值做对比dp[4] = dp[4] > dp[0] ? dp[0] +1: dp[0]dp[4] = dp[4] > dp[1] ? dp[1] +1: dp[1]dp[4] = dp[4] > dp[2] ? dp[2] +1: dp[2]dp[4] = dp[4] > dp[3] ? dp[2] +1: dp[3]最后
dp[4]取上面之中的最大值
所以仍是需要知道从数组第 1 个位置到最后一个位置的最优解，并每个值还要与之前值做比较，所以需要使用循环
var lengthOfLIS = function(nums) {
let result = 0
let dp = new Array(nums.length).fill(1)
for(let i =0; i<nums.length;i++){
for(let j = 0; j<i;j++){
if(nums[i]> nums[j]){
dp[i] = Math.max(dp[i], dp[j]+1)
}
}
result = Math.max(result, dp[i])
}
return result
};
# 最长回文子序列 (opens new window)
给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
示例 1:
输入:"bbbab"
输出:4
一个可能的最长回文子序列为 "bbbb"。
示例 2:
输入:"cbbd"
输出:2
一个可能的最长回文子序列为 "bb"。
解题思路
对于字符串 s 假设 dp[i][j] 表示数组下标 i-j 之间最长回文子序列
那么计算 dp[m][n] 的最长子序列的方式有几种情况：
s[m]===s[n]，那么dp[m][n] = dp[m+1][n-1]+2s[m]!==s[n]，那么dp[m][n]取现在有区间的最长回文子序列的最大值，dp[m][n]之间的最大区间有dp[m+][n]和dp[m][n-1]，所以此时dp[m][n] = Math.max(dp[m+1][n], dp[m][n-1])要得到
dp[m][n]，得从dp[0][0]开始计算到dp[m][n]
/**
* @param {string} s
* @return {number}
*/
var longestPalindromeSubseq = function(s) {
let dp = new Array(s.length).fill('').map(() => new Array(s.length)) // 定义 dp
for(let n = 0; n<s.length;n++){ // 从头开始遍历
for(let m = n;m>=0;m--){ // 外层的值依赖内层的值，所以从里到外遍历
if(m===n){ // 坐标相等，表示同一个数，dp[m][n] = 1
dp[m][n] = 1
} else if(s[m] === s[n]){ // 字符相等
dp[m][n] = (n-m===1) ? 2: dp[m+1][n-1]+2 // 如果是相邻的字符 dp[m][n] = 2，否则 [m][n] = dp[m+1][n-1]+2
} else{
dp[m][n] = Math.max(dp[m+1][n], dp[m][n-1]) // 取[m-n] 区域内的最大值
}
}
}
return dp[0][s.length-1]
};
# 5. 最长回文子串 (opens new window)
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
示例 3：
输入：s = "a"
输出："a"
示例 4：
输入：s = "ac"
输出："a"
解题思路
此题思路跟 [最长回文子序列] 一样，要解得最长回文字串，那么就得知道哪些是回文串，所以对于字符串 s 定义 dp[i][j]，表示数组下标 i到j 之间是否是回文串
那么计算 dp[m][n] 是否是回文串的情况有有：
s[m]===s[n] && dp[m+1][n-1]s[m]===s[n] && (n-m<2)，n-m=0表示s[m]和s[n]是同一个数，n-m=1表示s[m]和s[n]是两个相邻的数，要得到
dp[m][n]，得从dp[0][0]开始计算到dp[m][n]
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let res = ''
let db = new Array(s.length).fill('').map(() => new Array(s.length))
for(let i=0; i<s.length;i++){
for(let j=i;j>=0;j--){
if(s[i] === s[j]&&(i-j)<2){
db[j][i] = true
} else if(s[i] === s[j]&&db[j+1][i-1]){
db[j][i] = true
}
if(db[j][i] && (i-j+1)>res.length){ // 如果是回文串，取这个回文串如果比 res 大的话，就进行保存
res = s.substring(j,i+1)
}
}
}
return res
};
# 647. 回文子串 (opens new window)
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入："abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入："aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
思路
要获取多少回文子串，那么我需要知道两个条件
这个字符串可以分成哪些子串
字符串两两之间是否回文串
对于第二点，其实就同 [5. 最长回文子串] 题目一样，建立 dp，计算得到所有的 dp[m][n] 是否是回文串
// 建立 dp 的代码
var countSubstrings = function(s) {
let dp = new Array(s.length).fill('').map(() => new Array(s.length))
for(let i=0; i<s.length;i++){
for(let j=i;j>=0;j--){
if(s[i] === s[j]&&(i-j)<2){
dp[j][i] = true
} else if(s[i] === s[j]&&dp[j+1][i-1]){
dp[j][i] = true
}
}
}
};
对于子串，其实循环时得到的dp[j][i]时，[j][i] 就是子串了，所以这题其实这题跟 [5. 最长回文子串] 就是一样的
/**
* @param {string} s
* @return {number}
*/
var countSubstrings = function(s) {
let count = 0
let dp = new Array(s.length).fill('').map(() => new Array(s.length))
for(let i=0; i<s.length;i++){
for(let j=i;j>=0;j--){
if(s[i] === s[j]&&(i-j)<2){
dp[j][i] = true
} else if(s[i] === s[j]&&dp[j+1][i-1]){
dp[j][i] = true
}
if(dp[j][i]){
count++
}
}
}
return count
};
# 131. 分割回文串 (opens new window)
动态规则+回溯
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
思路
跟之前的题目类似，得先定义 dp 得到所有两两字符是否是回文串
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function(s) {
let bp = new Array(s.length).fill('').map(() => new Array(s.length))
for(let i = s.length-1;i>=0;i--){
for(let j = i;j<s.length;j++){
if(j-i<2 && s[i]===s[j]){
bp[i][j] = true
} else if(bp[i+1][j-1] && s[i]===s[j]){
bp[i][j] = true
} else{
bp[i][j] = false
}
}
}
let res = []
let tem = []
let walk = (start) => {
if(start === s.length){
res.push([...tem])
return
}
for(let i=start; i<s.length;i++){
if(!bp[start][i]){
continue
}
tem.push(s.substring(start,i+1))
walk(i+1)
tem.pop()
}
}
walk(0)
return res
}