动态规划合集一

整理了一些 leetcode上面的动态规则相关的题目，这是第一个合集，对于动态规划，转移方程最重要，所以每个题目都给出了转移方程。

v[i]是第i个元素的值。v[i][j]是第i行，第j列元素的值。

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

dp[i]表示包含第i个元素的和的最大值

let nums = [1, 2, 6]
let dp = new Array(nums.length)
dp[0]=nums[0]
for (let i=1;i<nums.length;i++>) {
  dp[i] = Math.max(dp[i - 1] + nums[i], nums[i])
}
return Math.max(...dp)
复制代码

可以简化为 O(n)的存储空间

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

dp[i]=dp[i-1]+dp[i-2]
dp[n-1] 即是解
复制代码

买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

最简单的想法就是找到全局最低，全局最高，一减完事。不过为了练习一下动态规划的想法，需要递推一下。

因为只能买卖一次，所以可以记录前面已经产生的最低值，今天的值最低价的差就是今天卖出所得的收益。把今天的收益和前面的最大收益比较，取最大值作为今天能获得的最大收益。

dp[i]表示第i可以获取的最大收益,MIN表示前i天的最低价。

dp[i]=max(v[i]-MIN,dp[i-1])
复制代码

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

输入: [1,2,3,1]

输出: 4

解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

dp[i]表示偷窃第i个房屋所能获取的最大现金

dp[i]=max(dp[i-2]+v[i],dp[i-1])
复制代码

最长回文串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

dp[i][j]，从i到j是否为回文

dp[i][j]=dp[i+1][j-1]&&dp[i]===dp[j]
复制代码

还可以用中心扩散法，一共有 n+n-1=2n-1个中心，n是奇数回文串的中心个数，n-2是偶数回文串的中心个数分别扩散 O(n2)

暴力法。有n(n-1)/2个子串(需要看一下排列组合），验证是否为回文是O(n)，整个为 O(n3)

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

dp[i][j]，到达第i行第j列所有路径数

dp[i][j]=dp[i-1][j]+dp[i][j-1]
复制代码

不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

dp[i][j]，到达第i行第j列所有路径数。有障碍物路径就是0。

dp[i][j] = isOk ? ( dp[i-1][j] + dp[i][j-1] ) : 0
复制代码

最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

dp[i][j]，到达第i行第j列路径的最小和

dp[i][j] = min( dp[i-1][j],dp[i][j-1] ) + v[i][j]

可以不用另外的存储空间，直接在数据数组上修改即可。

解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26
复制代码

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
复制代码

和爬楼梯问题是一样的，只是加了限制条件。假定字符串总是有效的,特殊考虑一下0

if (v[i] == 0) {
  dp[i] == 0
}
else if (`${v[i - 1]}${v[i]}` <= 26) {
  dp[i] = dp[i - 1] + dp[i - 2]
}
else {
  dp[i] = dp[i - 1]
}
复制代码

三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上

dp[i][j]，到达第i行第j列最小和

dp[i][j]=min(dp[i+1][j],dp[i][j+1])+v[i][j]

dp[0][0]即是解

单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

1. 拆分时可以重复使用字典中的单词。
2. 你可以假设字典中没有重复的单词。

dp[i]表示前i个字符是否可以拆分，dp[s.length-1]即为解

判断是否可以拆分用两段法，从中间砍一刀，看左右两段是否满足。 从第0个位置开始每个位置尝试砍一刀，分别看[0,j],[j,i]是否满足，直到满足或到末尾。

时间复杂度，因为外层需要遍历一次s，内层需要遍历[0，i]的每个位置，所以是O(n2)

乘积最大子序列

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
复制代码

dp[i][0]是包含第i个元素的最大乘积，dp[i][1]是包含第i个元素的最小乘积

if (v[i] == 0) {
  dp[i][0] = 0
  dp[i][1] = 0
}
dp[i][0] = max(v[i], dp[i - 1][0] * v[i],dp[i - 1][1] * v[i])
dp[i][1] = min(v[i], dp[i - 1][0] * v[i],dp[i - 1][1] * v[i])
复制代码

打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
    偷窃到的最高金额 = 1 + 3 = 4 。
复制代码

环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃，因此可以把此环状排列房间问题约化为两个单排排列房间子问题

在不偷窃第一个房子的情况下（即 nums[1:]nums[1:]）

在不偷窃最后一个房子的情况下（即 nums[:n-1]nums[:n−1]

综合偷窃最大金额： 为以上两种情况的较大值

完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

这和找零问题是一样的，只不过是把零钱改成放平方数

dp[i]且示组成第i个元素所需要的最少平方数。

dp[i]=min(dp[i-所有可以的平方数])

var dp[0] = 0, dp[1] = 1
for (var i = 2; i < n; i++) {
  //最环的情况就是解全是1
  dp[i] = i 
  for (var j = 1; j * j < i; j++) {
    dp[i] = Math.min(dp[i - j * j], dp[i])
  }
}
复制代码

最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

只要是前面比v[i]小的数，都可以和v[i]构成最长上升子序列，所以需要在所有可能中找最大值

var v = [1, 2, 5, -1, -2, 6]
var dp = [1]
for (var i = 1; i < v.length; i++) {
  dp[i] = 1 //最环的情况，前面都比自己大，长度1
  for (var j = 0; j < i; j++) {
    if (v[i] > v[j]) {
      dp[i] = max(dp[j] + 1, dp[i])
    }
  }
}
复制代码

还有nlogn的方案。每找到大的数，就追加。小的数覆盖前面的第一个比自己大的数。原理就是巧妙的复用了空间，把最有潜力的一组数放进来，数组的长度就是答案。新来的数，如果比老的一组数的最大值还大，就更新数组长度，也就是更新了答案。新来的，如果比老的最大值小，那就是潜力数据了。

最佳买卖股票时机含冷冻期

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:
输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
复制代码

这和前面的打家劫舍是一样的。就是表述不一样而已。

dp[i] = max(dp[i-2] + v[i],dp[i-1])
复制代码

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

从金额0开始正推。如果硬币不够，比如只有 2的硬币，f(0)=0f(1-2)=maxValue，相当于是说无法由当前硬币组成面值1，后面用到1的时候结果就是maxValue，相当于给没有的币加了一个权重，用到没有的币或无法合成的币值，最小币数是maxValue+1,取最小值，结果就是 maxValue，到最后一步，如果没有可用的币，结果就是 maxValue

let coins = [1, 2, 5], n = 11
let dp = new Array(coins.length).fill(n)
dp[0] = 0
for (let i = 1; i <= n; i++) {
  for (let coin of coins) {
    if (coin <= i) {
      dp[i] = Math.min(dp[i], dp[i - coin] + 1)
    }
  }
}
return dp[n] === n ? -1 : dp[n]
复制代码

整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

和割绳子原理一样。

dp[2] = 1
//i是正整数 i
for (var i = 3; i < n; i++) {
  //最小值就是全是1的情况，乘积也是1
  dp[i] = 1
  //j是分出来的数，这里 j<i/2 会更快些，不过容易出bug，直接 j<i 就行
  for (var j = 2; j < i; j++) {
    dp[i] = Math.max(dp[i], dp[j] * (i - j))
  }
}