数据结构与算法-动态规划

发表于 | 分类于

title: 剑指offer-动态规划
date: 2020-06-12 14:42:25
tags: Algorithms

categories: Algorithms

分治策略：将原问题分解为若干个规模较小但类似于原问题的子问题（Divide），「递归」的求解这些子问题（Conquer），然后再合并这些子问题的解来建立原问题的解。

动态规划: 动态规划其实和分治策略是类似的，也是将一个原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。 区别在于这些子问题会有重叠，一个子问题在求解后，可能会再次求解，于是我们想到将这些子问题的解存储起来，当下次再次求解这个子问题时，直接拿过来就是。 其实就是说，动态规划所解决的问题是分治策略所解决问题的一个子集，只是这个子集更适合用动态规划来解决从而得到更小的运行时间。 即用动态规划能解决的问题分治策略肯定能解决，只是运行时间长了。因此，分治策略一般用来解决子问题相互对立的问题，称为标准分治，而动态规划用来解决子问题重叠的问题。

动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如这里的统计方案数的问题，它们都存在一定的递推性质。前者的递推性质还有一个名字，叫做 「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数。所以在遇到求方案数的问题时，我们可以往动态规划的方向考虑。

动态规划两个重要的问题是：记录的状态是什么、状态的更新（之前状态如何递推当前的状态）。

https://www.zhihu.com/question/39948290/answer/883302989
https://www.zhihu.com/question/39948290

1. 连续子数组最大和

题目描述

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

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解题思路
这是一道典型的动态规划题目。 最大子数组的和一定是由当前元素和之前最大连续子数组的和叠加在一起形成的。 

假设dp[i]代表以当前元素a[i]为截止点的连续子序列的最大和;
若dp[i-1]>0, dp[i]=a[i]+dp[i-1], 因为当前数加上正数一定会变大;
若dp[i-1]<0, dp[i]=a[i], 因为当前数加上负数一定会变小；
使用max记录最大的dp值。 max=Math.max(max, dp[i]).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    
class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        int max = nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for(int i = 1; i < nums.length; i++){
            dp[i] = Math.max(nums[i] + dp[i-1], nums[i]);
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

2. 打家劫舍（LeetCode 198）

题目描述：

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

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

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        if(nums.length == 1){
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for(int i=2; i<nums.length; i++){
            dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
        }
        return dp[nums.length - 1];
    }
}

3. 打家劫舍 II（LeetCode 213）

题目描述：

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

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

解题思路：

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

  • 在不偷窃第一个房子的情况下（即 nums[1:]nums[1:]），最大金额是 p1；
  • 在不偷窃最后一个房子的情况下（即 nums[:n-1]nums[:n−1]），最大金额是 p2

​
综合偷窃最大金额： 为以上两种情况的较大值，即 max(p1,p2)max(p1,p2) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
   
class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        if(nums.length == 1){
            return nums[0];
        }
        return Math.max(singleRob(Arrays.copyOfRange(nums, 0, nums.length-1)), singleRob(Arrays.copyOfRange(nums, 1, nums.length)));
    }
    public int singleRob(int[] nums){
        int pre = 0, cur = 0;
        for(int i = 0; i < nums.length; i++){
            int tmp = cur;
            cur = Math.max(nums[i] + pre, cur);
            pre = tmp;
        }
        return cur;
    }
}

4. 打家劫舍 III (LeetCode 337)

题目描述：

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

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

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

解题思路：
简化问题：一棵二叉树，树上的每个点都有对应的权值，每个点有两种状态（选中和不选中），问在不能同时选中有父子关系的点的情况下，能选中的点的最大权值和是多少。

我们可以用 f(o)表示选择 o 节点的情况下，o节点的子树上被选择的节点的最大权值和；g(o)表示不选择 o 节点的情况下，o 节点的子树上被选择的节点的最大权值和；l 和 r 代表 o 的左右孩子。

  • 当 o 被选中时，o 的左右孩子都不能被选中，故 o 被选中情况下子树上被选中点的最大权值和为 l 和 r 不被选中的最大权值和相加，即 f(o) = g(l) + g(r)。
  • 当 o 不被选中时，o 的左右孩子可以被选中，也可以不被选中。对于 o 的某个具体的孩子 x，它对 o 的贡献是 x 被选中和不被选中情况下权值和的较大值。故 (o)=max{f(l),g(l)}+max{f(r),g(r)}。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
     
class Solution {
    public int rob(TreeNode root) {
        if(root == null){
            return 0;
        }
        int[] ret = pathRob(root);
        return Math.max(ret[0], ret[1]);
    }
    public int[] pathRob(TreeNode root){
        if(root == null){
            return new int[]{0,0};
        }
        int[] l = pathRob(root.left);
        int[] r = pathRob(root.right);
        int select = root.val + l[1] + r[1];  
        int unselect = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{select, unselect};
    }
}

2. 正则表达式

题目描述

请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

方法一：递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
         
class Solution {
    public boolean isMatch(String s, String p) {
        boolean flag = match(s, p, 0, 0);
        return flag;
    }
    public boolean match(String s, String p, int i, int j){
        if(i==s.length() && j==p.length()){
            return true;
        }
        if(i<s.length() && j>=p.length()){
            return false;
        }
        if(j+1<p.length() && p.charAt(j+1)=='*'){
            if(i<s.length() && (p.charAt(j)=='.' || s.charAt(i)==p.charAt(j))){
                return match(s, p, i, j+2) || match(s, p, i+1, j);
            }else{
                return match(s, p, i, j+2);
            }
        }
        if(i<s.length() && (s.charAt(i)==p.charAt(j) || p.charAt(j)=='.')){
            return match(s, p, i+1, j+1);
        }
        return false;
    }
}

方法二：动态规划

1
2

3. 最长有效括号

题目描述：

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”

方法一：动态规划

我们定义 dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。我们将 dp 数组全部初始化为 0 。显然有效的子串一定以 ‘)’ 结尾，因此我们可以知道以 ‘(’ 结尾的子串对应的 dp 值必定为 0 ，我们只需要求解 ‘)’ 在 dp 数组中对应位置的值。

我们从前往后遍历字符串求解 dp 值，我们每两个字符检查一次：

  1. s[i] = ‘)’ 且 s[i - 1] = ‘(’，也就是字符串形如 “……()”“……()”，我们可以推出：

    dp[i]=dp[i−2]+2

我们可以进行这样的转移，是因为结束部分的 “()” 是一个有效子字符串，并且将之前有效子字符串的长度增加了 2 。

  1. s[i] = ‘)’ 且 s[i - 1] = ‘)’，也就是字符串形如 “……))”“……))”，我们可以推出：
    如果 s[i−dp[i−1]−1]=‘(’，那么

    dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2

我们考虑如果倒数第二个 ‘)’ 是一个有效子字符串的一部分（记作 sub_ssubs）对于最后一个 ‘)’ ，如果它是一个更长子字符串的一部分，那么它一定有一个对应的 ‘(’ ，且它的位置在倒数第二个 ‘)’ 所在的有效子字符串的前面（也就是 sub_ssub
s的前面）。因此，如果子字符串 sub_ssubs的前面恰好是 ‘(’ ，那么我们就用 2 加上 sub_ssubs的长度（dp[i−1]）去更新 dp[i]。同时，我们也会把有效子串 “(sub_s)”“(subs)” 之前的有效子串的长度也加上，也就是再加上 dp[i−dp[i−1]−2]。

最后的答案即为 dp 数组中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
       
class Solution {
    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];  //记录到第i个字符最长有效括号子串的长度
        int maxn = 0;  
        for(int i=1; i<s.length(); i++){
            if(s.charAt(i) == ')'){
                if(s.charAt(i-1) == '('){
                    dp[i] = (i>=2? dp[i-2]:0) + 2;
                }else if(i-dp[i-1]>0 && s.charAt(i-dp[i-1]-1)=='('){
                    dp[i] = dp[i-1] + (i - dp[i-1] >=2 ? dp[i-dp[i-1]-2] : 0) + 2;
                }
            }
            maxn = dp[i]>maxn? dp[i]:maxn;
        }
        return maxn;
    }
}
  • 时间复杂度： O(n)
  • 空间复杂度： O(n)

方法二：栈

始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：

  • 对于遇到的每个 ‘(’ ，我们将它的下标放入栈中
  • 对于遇到的每个 ‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号：
    • 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」
    • 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」

我们从前往后遍历字符串并更新答案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
   
public class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
}
  • 时间复杂度： O(n)
  • 空间复杂度： O(n)

4. 不同路径1

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？

1.png

解法：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
   
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        int up, le;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i == 0 && j == 0){
                    continue;
                }
                up = i-1 >= 0 ? dp[i-1][j] : 0;
                le = j-1 >= 0 ? dp[i][j-1] : 0;
                dp[i][j] = up + le;
            }
        }
        return dp[m-1][n-1];
    }
}

不同路径2

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
   
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length, n=obstacleGrid[0].length;
        if(obstacleGrid[m-1][n-1]==1 || obstacleGrid[0][0]==1){
            return 0;
        }
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        int up = 0;
        int le = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i==0 && j==0){
                    continue;
                }
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }else{
                    up = i-1 >= 0 ? dp[i-1][j] : 0;
                    le = j-1 >= 0 ? dp[i][j-1] : 0;
                    dp[i][j] = up + le;
                }
            }
        }
        return dp[m-1][n-1];
    }
}
  • 时间复杂度：O(mn) 遍历一遍二维数组
  • 空间度咋读：O(mn) 存储一个二维数组

算法空间复杂度优化：

由于每个状态 dp[i][j] 仅有 dp[i-1][j] 和 dp[i][j-1]两个状态决定，所以可以优化状态的存储空间，仅使用一个一维数组进行存储，即数组滚动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
  
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[] f = new int[m];
        f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    f[j] += f[j - 1];
					// 其实该状态更新可以细化为 f[j] = f[j] + f[j - 1];  
					//  - 等号右边f[i]就代表上一行中 dp[i-1][j] 值， 即从上面来；
					//  - 等号右边f[i]就代表 dp[i][j-1] 的值， 即从左面来。
                }
            }
        }
        return f[m - 1];
    }
}
  • 时间复杂度：O(mn) 遍历一遍二维数组
  • 空间度咋读：O(n) 存储一个一维数组