动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
动态规划的难点就是思路：
- 1、递归+记忆化 = 递推
- 2、状态的定义：opt[n],dp[n]...
- 3、状态转移方程：dp[n] = best_of(dp[n-1],dp[n-2],...)
- 4、最优子结构
动态规划 VS 回溯(递归) VS 贪心
- 回溯(递归)：重复计算
- 贪心：永远局部最优
- 动态规划：记录最优子结构，多种记录值
爬楼梯
不同路径 II
编辑距离
买卖股票的最佳时机
买卖股票的最佳时机 II
买卖股票的最佳时机 III
买卖股票的最佳时机 IV
一、爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
根据题目来看，如果想爬到第n层，可以从第n - 2层一次爬2阶，也可以从第n - 1层一次爬1阶。
那么设爬到第n层的方法数为f(n),则f(n) = f(n - 1) + f(n - 2)
很容易可以看出，这是最简单的动态规划例子：斐波拉契(Fibonacci)数列问题，其状态转移方程为dp(n) = dp(n - 1) + dp(n - 2)
我们很容易想到用递归来做
var climbStairs = function(n){
return n <= 2 ? n : (climbStairs(n - 1) + climbStairs(n - 2))
}
然而在leetcode提交后却是超时，原因就在于在climbStairs(n - 1)和climbStairs(n - 2)的递归过程中，存在很多重复计算，其时间复杂度是o(2n)
而动态规划相对于递归，有个明显的特点就是：记忆化
递归+记忆化 = 递推
所以我们可以添加一个缓存数组，将每次计算的值缓存下来
var climbStairs = function(n){
let dp = [1,2]
for(let i = 2;i < n; i++){
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n - 1]
}
时间复杂度则为o(n)
二、 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
image
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入: [
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
动态规划之所以难，就在于其思路，这道题目是中等难度。
其难点就在于思路，我们可以反着想，不去想机器人往哪里走，而去想机器人从哪里来，然后一直回溯。
由题目可知，机器人只能从左或者从上走过来
就很容易得出其状态转移方程为:
如果当前没有障碍物，dp[m][n] = dp[m - 1][n] + dp[m][n - 1]
如果有障碍物，则dp[m][n] = 0
var uniquePathsWithObstacles = function(obstacleGrid) {
if(obstacleGrid.length == 0) return 0
if(obstacleGrid[0][0]) return 0
let dp = []
for(let i = 0; i < obstacleGrid.length; i++){
dp[i] = []
}
dp[0][0] = 1
for(let i = 0; i < obstacleGrid.length; i++){
for(let j = 0; j < obstacleGrid[0].length; j++){
if(!i && !j) continue
if(obstacleGrid[i][j]) dp[i][j] = 0
else dp[i][j] = (i ? dp[i - 1][j] : 0) + (j ? dp[i][j - 1] : 0)
}
}
return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 1]
};
时间复杂度为o(m*n)
以上两题感觉动态规划好像没那么难，思路并不是很难想？
然而并不是，因为上面两题很‘动态规划’，本身属于比较契合动态规划思路的
而有的题目，思路很难想，很难下手
比如：
三、 编辑距离
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1:
输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2:
输入: word1 = "intention", word2 = "execution"
输出: 5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
这算是比较经典的动态规划题目了，难度为困难，不过leetcode通过率还挺高的。
DP两部曲
1、首先找状态定义，这里初看题，很容易是会定义成用DP[i]，然而这样是没办法解决的，应该是DP[i][j]，表示为单词1的前i个字符要转换成单词2的前j个字符，最少需要的步数。
2、然后定义状态转移方程
状态定义好后，状态转移方程也就不难列了。
如果单词1第i+1个字符和单词2第j+1个字符相同，那么就不用操作，则DP[i + 1][j + 1] = DP[i][j];
如果不相同,则有三种可能操作，即增，删，替换。则取这三种操作的最优值，即dp[i + 1][j + 1] = 1 + Math.min(dp[i][j], Math.min(dp[i][j + 1], dp[i + 1][j]));
即可得出代码如下：
var minDistance = function(word1, word2) {
let m = word1.length, n = word2.length;
let dp = new Array();
for(let i = 0; i <= m; i++){
dp[i] = new Array();
dp[i][0] = i;
}
for(let i = 0; i <= n; i++){
dp[0][i] = i;
}
for(let i = 1; i <= m; i++) {
for(let j = 1; j <= n; j++) {
if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
}
}
return dp[m][n];
};
时间复杂度为o(m*n)
四、股票买卖问题
这是leetcode上的经典的股票买卖系列问题
买卖股票的最佳时机
买卖股票的最佳时机 II
买卖股票的最佳时机 III
前两题比较简单，第三题包含在第四题中。
下面看下第四题
买卖股票的最佳时机 IV
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:
输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
首先，如果k大于给定的数组数量，就意味着可以尽可能多的买卖，也就是和第二题一致了。
而如果k小于数组数量，动态规划两部曲
- 首先找状态定义，简单的dp[i]并不能满足要求，因为有买卖两种形式，所以我们应该设置两个状态定义buy[i]和sell[i],i <= k
假设初始总金额为0，这里直接用dp[0][i]来表示在某天买入第i次后的总金额(可能会是负数)，用dp[1][i]表示在某天卖出第i次后的总金额 - 然后确立状态转移方程：
在某天买入第i次，应该是上次卖出后的总金额减去当天股票价格p和上次买入后的总金额的最大值
即dp[0][i] = Math.max(dp[0][i], (i ? dp[1][i - 1] : 0) - p)
而在某天卖出第i次，应该是上次买入后的总金额加上当天股票价格p和上次卖出后的总金额的最大值
即dp[1][i] = Math.max(dp[1][i], dp[0][i] + p);
则代码如下
var maxProfit = function(k, prices) {
if(prices.length <= 1 || k <= 0) return 0
if (prices.length/2 <= k) {
let maxProfit = 0;
for (let i = 1; i < prices.length; ++i) {
if (prices[i] > prices[i-1]) {
maxProfit += (prices[i] - prices[i-1]);
}
}
return maxProfit;
}
let dp = [new Array(k).fill(-Infinity),new Array(k).fill(0)]
for(let i = 0; i < prices.length; i++){
let p = prices[i];
for(let j = 0; j < Math.min(i + 1,k); j++){
dp[0][j] = Math.max(dp[0][j], (j ? dp[1][j - 1] : 0) - p);
dp[1][j] = Math.max(dp[1][j], dp[0][j] + p);
}
}
return dp[1].pop()
};
网友评论