2019 算法面试相关(leetcode)--动态规划(Dyna

动态规划(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 阶 + 1 阶
2. 2 阶
   示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 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(2ⁿ)

而动态规划相对于递归，有个明显的特点就是：记忆化

递归+记忆化 = 递推

所以我们可以添加一个缓存数组，将每次计算的值缓存下来

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()
};