Jinzhe Shan

动态规划专项练习-20190928

动态规划

目录：

动态规划

动态规划思考步骤：

​ 1 原问题： ​
​ 2 子问题： ​
​ 3 确认状态： ​
​ 4 初始状态： ​
​ 5 状态转移方程： ​
例1: 爬楼梯

例2: 打家劫舍

例3:最大子段和

例4：找零钱

例5：三角形数组和最小路径 （二维DP）

例6 ： 最长上升子序列

例7： 二维矩阵中左上角到右下角的最短路径和

例8:地牢游戏

动态规划解题步骤

核心思想是递推，难点在于想起出 状态 dp[i] 代表什么，然后构造状态转移矩阵，利用初始条件递推出最终结果

  1. 将原问题拆分成子问题
  2. 确认状态
  3. 确认边界状态（初始条件）
  4. 状态转移方程

例1: 爬楼梯

LeetCode 70. Climbing Stairs

四步走:

  1. 将原问题拆分成子问题

  2. 原问题：在爬楼梯时，每次可向上走1阶台阶或2阶台阶，问有n阶楼 梯有多少种上楼的方式？

  3. 子问题：第三阶台阶有多少种方法？第四阶呢？

  4. 确认状态

第 i 个状态 即为第 i 阶台阶的所有走法数量

  1. 确认边界状态（初始条件）： 边界状态为1阶台阶与2阶台阶的走法，1 阶台阶有1种走法，2阶台阶有2种走法， 即dp[1] = 1，dp[2] = 2。

  2. 状态转移方程 dp[i] = dp[i-1] + dp[i-2]; (i>=3)

解题代码：

public int climbStairs(int n) {
    if(n==1){
        return 1;
    }
    int[] dp = new int[n+1];
    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3;i<=n;i++)
        dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

例2: 打家劫舍

动态规划思考步骤：

1 原问题：

LeetCode 198. House Robber

在一条直线上，有n个房屋，每个房屋中有数量不等的财宝，有一个盗 贼希望从房屋中盗取财宝，由于房屋中有报警器，如果同时从相邻的两个房屋中盗取财宝就会触发报警器。问在不触发报警器的前提下，最多可获取多少财宝？例如 [5，2，6，3，1，7]，则选择5，6，7

2 子问题：

  1. 只考虑前两个房间时，谁大选谁
  2. 考虑第三个房间
  3. 如果偷第三个房间，则意味着第二个房间不投，也就是第三个房间值 + 第一个房间的宝藏数量
  4. 如果不偷第三个房间，则宝藏数量等于前两个房间宝藏数量

3 确认状态：

int [] nums; // 各个房间的宝藏数

int [] flags = new int [n]; // 记录各个房间有没有被偷，若flag = 0 则没偷， flag = 1 则偷了。

int [] dp = new int [n]; // dp[i]表示前i个房间偷到的最大宝藏数

4 初始状态：

第一个房间：

  • Condistion 1 ：dp[0] = nums[0] ; flags[0] = 1;
  • Condistion 2 ：dp[0] = 0; flags[0] = 0;

第二个房间：

  • Condistion 1 ：when flags[1] = 1; dp[1] = nums[1];
  • Condistion 2 ：whenflags[1] = 0; dp[1] = dp[0];
  • 选 Condistion 1 还是 Condistion 2呢？ 比较 两种情况下dp[1]的大小

推广到前i个房间: (i>=2)

  • when flags[i] = 1, dp[i] = nums[i] + dp[i-2]
  • when flags[i] = 0; dp[i] = dp[i-1]

5 状态转移方程：

dp[0] = nums[0];
dp[1] = max(nums[0],nums[1]);
for(int i = 2;i<n;i++)
    dp[i] = max(nums[i] + dp[i-2],dp[i-1])

解题代码

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0)
            return 0;
        int [] dp = new int[nums.length];
        dp[0] = nums[0];
        // 每次做数组判定时都需要做数组边界判定，防止越界
        if(nums.length < 2)
            return nums[0];
        dp[1] = (nums[0]>nums[1]) ? nums[0] : nums[1];
        for(int i = 2;i<nums.length;i++)
            dp[i] = ((nums[i] + dp[i-2]) > dp[i-1]) ? (nums[i]+dp[i-2]) : dp[i-1];
        return dp[nums.length-1];
    }
}

例3:最大子段和

动态规划思考步骤：

1 原问题

LeetCode 53. Maximum Subarray

给定一个数组，求这个数组的连续子数组中，最大的那一段的和。

如数组[-2,1,-3,4,-1,2,1,-5,4] 的子段为：

[-2,1]、[1,-3,4,-1]、[4,-1,2,1]、...、[-2,1,-3,4,-1,2,1,-5,4]，和最大的是[4,1,2,1]，为6。

Input: int [] nums = [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

2 子问题

  1. 只考虑第一个元素，则最大子段和为其本身 DP[0] = nums[0]
  2. 考虑前两个元素，最大子段和为 nums[0],num[1]以及 nums[0] + num[1] 中最大值 设为DP[1]
  3. 考虑前三个元素，如何求其最大子段和？还是分为两种情况讨论，第三个元素在最后的字串内吗？
  4. 若第三个元素也包含在最后的字串内，则DP[2] = Max(DP[1]+nums[2] , nums[2])

3 确认状态

DP[i] 为 以nums[i]结尾的子段的最大最短和

例如 DP[1]则为以nums[1]结尾的最大字段和

4 初始状态

dp[0] = nums[0]

dp[1] = max(dp[0]+nums[1] , nums[1])

5 状态转移方程：

dp[i] = max(dp[i-1]+nums[i],nums[i])

解题代码：

public class lc53_MaximumSubarray {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if(len == 0)
            return 0;
        int [] dp = new int[len];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i<len;i++){
            dp[i] = (dp[i-1]+nums[i] > nums[i]) ? dp[i-1]+nums[i] : nums[i];
            if (dp[i]>max)
                max = dp[i];
        }
        return max;
    }
}

例4：找零钱

LeetCode 322. Coin Change

已知不同面值的钞票，求如 何用最少数量的钞票组成某个金额，求可 以使用的最少钞票数量。如果任意数量的已知面值钞票都无法组成该金额， 则返回-1。

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Input: coins = [2], amount = 3
Output: -1

动态规划解题步骤：

  1. 将原问题拆分成子问题
  2. 已知什么？显而易见，钞票的金额都只需要其本身1张即可
  3. 如何在已知钞票的情况下构造出 金额X需要的最少钞票组合
  4. 确认状态
  5. DP[0] - DP[amount] 表示构造金额amount需要的最小钞票数
  6. 确认边界状态（初始条件）
  7. DP[coin] = 1 其他的都未知初始值设为 -1
  8. 例如coins = [1, 2, 5], amount = 11 已知 dp[1]、dp[2]、dp[5] =1
  9. 现在已知 DP[coin] 需要求出每一个DP[amount]
  10. 状态转移方程
  11. dp[i] = min(dp[i-1], dp[i-2], dp[i-5]) + 1

解题代码：（java）

    public int coinChange(int[] coins, int amount) {
        int len = coins.length;
        if (len == 0 || amount<0)
            return -1;
        if (amount==0)
            return 0;
        int [] dp = new int[amount+1];
        for (int i = 0; i <= amount; i++){
            dp[i] = -1;
        }
        for (int i = 0; i< len;i++){
            if(coins[i] == amount)
                return 1;
            if(coins[i] < amount)
                dp[coins[i]] = 1;
        }
        // State Transfer Function
        for(int i = 1; i <= amount;i++){
            for (int j = 0; j < len; j++){
                if (i - coins[j] >= 0 && dp[i - coins[j]] != -1){
                    if (dp[i] == -1 || dp[i] > dp[i - coins[j]] + 1){
                        dp[i] = dp[i - coins[j]] + 1;
                    }
                }
            }
        }
        return dp[amount];
    }

例5：三角形数组和最小路径 （二维DP）

LeetCode 120. Triangle

动态规划解题步骤：

  1. 原问题：

给定一个二维数组，其保存了一个数字三角形 triangleMatrix[] []，求从数字三角形顶端到底端各数字和最小的路径之和，每次可以向下走相邻的两个位置

For example, given the following triangle

[ [2], [3,4], [6,5,7], [4,1,8,3] ]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

  1. 子问题：

到达每一个节点的最短路径和是多少？知道上一层每一个节点的最短路径和数组可以递推出下一层的最短路径和吗？

  1. 确认状态

构造一个大小与三角形矩阵一致的最短路径和矩阵 DP[ ] [ ] ，DP[i] [j] 表示到达第i行 第j列节点的最短路径和

  1. 初始条件和边界条件

思考：从上往下走 和 从下往上走本质是一样的，怎么做实现起来会更方便呢？

从下往上，最短路径矩阵底层所有元素值就等于三角形矩阵底层所有元素值，然后往上递推。

每一个节点的最短路径值只需要考虑它下一层正下方和右下方最短路径矩阵中哪个更小，与其相加即可

  1. 状态转移方程：

从下往上递推： DP[i] [j] = min(DP[i+1] [j], DP[i+1] [j+1]) + triangleMatrix [i] [j]

最终返回 DP[0] [0]

解题代码：（java）

import java.util.ArrayList;

public class lc120_Triangle {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
    /* // method 1 - modify the original list
        for(int i = triangle.size() - 2; i >= 0; i--)
            for(int j = 0; j <= i; j++)
                triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
        return triangle.get(0).get(0);
    */
        if (triangle.isEmpty())
            return 0;
        if (triangle.size() == 1)
            return triangle.get(0).get(0);
        int [][] dp = new int[triangle.size()][triangle.get(triangle.size()-1).size()];

        // Bottom level initialization
        for (int i =0;i<triangle.get(triangle.size()-1).size();i++)
            dp[triangle.size()-1][i] = triangle.get(triangle.size()-1).get(i);

        // From the last second line to the top line
        for(int i = triangle.size()-2; i >=0;i--){
            for (int j = 0; j<=i;j++){
                dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}

例6 ： 最长上升子序列

LeetCode 300. Longest Increasing Subsequence

动态规划解题步骤：

  1. 原问题：

已知一个未排序数组，求这个数组最长上升子序列的长度。 例如: [1, 3, 2, 3, 1, 4]， 其中有很多上升子序列，如[1, 3]、[1, 2, 3]、 [1, 2, 3, 4]等，其中最长的上升子序列长度为4。分别考虑O(n^2)与O(n*logn)两种复杂度算法

  1. 子问题： 到底怎么构造DP数组能够表示最长上升子序列的长度？

如果在nums[i] 前面按顺序比nums[i]小的数字有N个，则DP[i] = N+1 （1为其本身）

例如 nums[1] = 3， 往前找，有1个按递减顺序比我小的数字，则DP[1] = 1+1 = 2

例如 nums[5] = 4， 往前找，有3个依次递减的数字 【3,2,1】，则DP[5] = 3+1 = 4

  • 为了递推可以进行下去，比nums[i]小这个条件可以忽略，先找到前面最长的上升序列，然后找到有几个比当前节点nums[i]小的

    所以问题变成了维持一个到当前节点为止(包含当前节点)，最长的上升序列，然后与当前节点做比较，求得DP[i]

  • 再往深想一步，如何维持这个最长上升序列呢？ 只保留其长度len 和其中最大值max[i]是否就可以？

    此时，DP[i] = Max(（if nums[i]>max[j]）DP[j] + 1 )

  • 最终搞清楚了确认状态： DP[i]是以nums[i]结尾的最长上升子序列长度

    状态转移函数也很好理解：DP[i] = j 从 0 到 i-1，只要nums[j] < nums[i] 且 DP[i] < DP[j] + 1, DP[i] = DP[j] + 1

  • 确认状态：

DP[i] 表示到nums[i]为止最长上升序列的长度

从i=0开始往后递推，维持一个最长上升序列 increasingList []

最终搞清楚了确认状态： DP[i]是以nums[i]结尾的最长上升子序列长度

  1. 初始条件和边界条件：

DP[0] = 1 最大上升字串长度LIS = 1

  1. 状态转移方程：

DP[i] = j 从 0 到 i-1，只要nums[j] < nums[i] 且 DP[i] < DP[j] + 1, DP[i] = DP[j] + 1

只要 DP[i] > LIS, LIS = DP[i]

解题代码 1：（java）

class Solution {
    // solution 1 : time complexity = O(n^2)
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if (len == 0)
            return 0;
        // when index = i, the length of longest increasing subsequence
        int [] dp = new int[len]; 
        dp [0] = 1;
        int max = dp[0];
        for (int i = 0; i < len; i++){
            dp[i] = 1;
            for(int j = 0; j < i;j++){
                // State Transition Function
                if(nums[i] > nums[j] && dp[i] < dp[j]+1)
                    dp[i] = dp[j]+1;
            }
            if(dp[i]>max)
                max = dp[i];
        }
        return max;
    }
}

例7： 二维矩阵中左上角到右下角的最短路径和

LeetCode 64. Minimum Path Sum

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

动态规划解题步骤：

  1. 原问题：

已知一个二维数组，其中存储了非负整数，找到从左上角到右下角的一 条路径，使得路径上的和最小。(移动过程中只能向下或向右)

  1. 子问题

到达每一个节点的最小路径值是不是可以依次递推求出来？

  1. 确定状态和初始状态

状态为一个和输入矩阵一样大的DP矩阵，其中DP[i] [j]存到达节点[i] [j]的最短路径和,初始值设为-1表明没有遍历到

初始状态知道DP[0] [0] DP[0] [1] 和 DP[1] [0]

  1. 状态转移方程

DP[i] [j] = min(DP[i-1] [j] , DP[i] [j-1]) + input[i] [j]

解题代码：（java）

public class lc64_MinimumPathSum {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0)
            return 0;
        int row = grid.length;
        int col = grid[0].length;

        int[][] dp = grid;

        // state transaction function
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // initialization
                // Do not forget continue!
                if (i == 0 && j == 0) {
                    dp[i][j] = grid[0][0];
                    continue;
                }
                if (i == 0){
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                    continue;
                }
                if (j == 0){
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                    continue;
                }

                // normal
                dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
                System.out.println("i = " + i + " j = " + j + " DP = " +dp[i][j]);
            }
        }
        return dp[row - 1][col - 1];
    }
}

例8:地牢游戏

LeetCode 174. Dungeon Game

动态规划解题步骤：

  1. 原问题：

已知一个二维数组，左上角代表骑士的位置，右下角代表公主的位置， 二维数组中存储整数，正数可以给骑士增加生命值，负数会减少骑士的生命值，问骑士初始时至少是多少生命值，才可保证骑士在行走的过程中至少保持生命值为1。(骑士只能向下或向右行走)

  1. 子问题：

本题初看和例题6有点类似，而且最小初始血量也很好定义出来，为 1 - 当前血量

又因为要求最小血量为1，所以当前节点的最小血量应该为 max（1， 1 - 当前血量）

从左上往右下推初始血量很困难，但是从右下往左上可以轻松倒推出当前血量至少为多少才可以保证到达重点时血量不低于1。

  1. 确认状态 + 初始状态

DP[i] [j] 表示保证到达终点时血量不低于1的最小血量，最小值取 1 保证不在中途阵亡

这就意味着 DP[0] [0] 就是我们要求的最小初始血量

  1. 状态转移方程

从右下开始往左上走，每次只能向上或者向左

minHP = min(dp[i+1] [j] , dp[i] [j+1]) // 右边的 或者下边的最小血量

DP [i] [j] = max(1, 1 - minHP) // 1- minHP 是为了让自己活下来最小血量，1为最小值

解题代码：（java）

public class lc174_DungeonGame {
    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length == 0)
            return 0;
        int row = dungeon.length;
        int col = dungeon[0].length;

        int[][] dp = dungeon;
        int dp_min = 0;

        // state transaction function
        for (int i = row-1; i >=0; i--) {
            for (int j = col-1; j >=0 ; j--) {
                // initialization
                // Do not forget continue!
                if (i == row-1 && j == col-1) {
                    dp[i][j] = Math.max(1,1-dungeon[i][j]);
                    continue;
                }
                if (i == row-1 ){
                    dp[i][j] = Math.max(1,dp[i][j+1]-dungeon[i][j]);
                    continue;
                }
                if (j == col-1){
                    dp[i][j] = Math.max(1,dp[i+1][j]-dungeon[i][j]);
                    continue;
                }

                // normal
                dp_min= Math.min(dp[i][j+1], dp[i+1][j]);
                dp[i][j] = Math.max(1,dp_min-dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
}

动态规划总结：

这篇文章从28号晚上陆陆续续一直写到30号晚上，主要是基于小象学院 《面试算法LeetCode刷题班》中动态规划的一章，今天去官网看发现课程已经下架了，故将课程课件放在了我GitHub秋招面试准备repo中，有需要的朋友可以自己下载。

动态规划是很大一类算法题，也是各大互联网公司笔试面试中逃不掉的一个测试算法基本功的题型。本文只做了一个入门，动态规划系列文章随着我学习的深入，会陆续发布在专栏中。

愿诸君阅读愉快，学习进步。

Published

Category

interview

Tags

Contact