第13章动态规划 - 2. 动态规划问题汇总 - 《数据结构与算法》

LeetCode

区间 DP

字符串匹配问题

32. 最长有效括号

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

s		(	(	)
stack	-1	-1,0	-1,0,1	-1,0

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ')' && stack.size() > 1 && s.charAt(stack.peek()) == '(') {
                stack.pop();
                res = Math.max(res, i - stack.peek());
            } else {
                stack.push(i);
            }
        }
        return res;
    }
}

树形 DP

计数型 DP

计数型DP都可以以组合数学的方法写出组合数，然后dp求组合数

递推型 DP

所有线性递推关系都可以用矩阵快速幂做，可以O(logN)，最典型是斐波那契数列

概率型 DP

求概率，求数学期望

博弈型 DP

策梅洛定理，SG 定理，minimax。

1、翻转游戏

2、Nim游戏

3、石子游戏

记忆化搜索

本质是 dfs + 记忆化，用在状态的转移方向不确定的情况。

剑指 Offer

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

思路：
动态规划。

class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }
}

剑指 Offer 10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

思路：
动态规划。

class Solution {
    public int numWays(int n) {
        if (n == 0) return 1;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }
}

剑指 Offer 14- I. 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

思路：
①动态规划。找规律。

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n+1];
        if (n == 2) return 1;
        if (n == 3) return 2;
        if (n == 4) return 4;
        if (n == 5) return 6;
        if (n == 6) return 9;
        dp[4] = 4;
        dp[5] = 6;
        dp[6] = 9;
        for (int i = 7; i <= n; i++) {
            dp[i] = dp[i - 3] * 3;
        }
        return dp[n];
    }
}

剑指 Offer 14- II. 剪绳子 II

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

思路：
①动态规划。找规律。相比上一题，本题主要考察边界溢出的问题。动态规划的中间结果容易溢出。

class Solution {
    public int cuttingRope(int n) {
        long[] dp = new long[n+1];
        if (n == 2) return 1;
        if (n == 3) return 2;
        if (n == 4) return 4;
        if (n == 5) return 6;
        if (n == 6) return 9;
        dp[4] = 4;
        dp[5] = 6;
        dp[6] = 9;
        for (int i = 7; i <= n; i++) {
            dp[i] = (dp[i - 3] * 3) % 1000000007;
        }
        return (int) dp[n];
    }
}

剑指 Offer 42. 连续子数组的最大和

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。

思路1：
动态规划。0 表示不包括当前元素的子数组的和的最大值，1表示包括当前元素的子数组的和的最大值。
执行用时：6 ms, 在所有 Java 提交中击败了15.32%的用户
内存消耗：48.5 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }
        int[][] dp = new int[len][2];
        dp[0][0] = nums[0];
        dp[0][1] = nums[0];
        dp[1][0] = nums[0];
        dp[1][1] = Math.max(nums[1], dp[0][1] + nums[1]);
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = Math.max(nums[i], dp[i - 1][1] + nums[i]);
        }
        return Math.max(dp[len - 1][0], dp[len - 1][1]);
    }
}

思路2：
贪心算法。维护前面子数组的和的最大值 pre，和当前最大值 cur。
执行用时：1 ms, 在所有 Java 提交中击败了99.06%的用户
内存消耗：46.5 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxRes = nums[0];
        for(int a : nums) {
            pre = Math.max(pre+a, a);
            maxRes = Math.max(maxRes,pre);
        }
        return maxRes;
    }
}

剑指 Offer 46. 把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

思路：
动态规划。

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int[] dp = new int[s.length()+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= s.length(); i ++){
            String temp = s.substring(i-2, i);
            if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0)
                dp[i] = dp[i-1] + dp[i-2];
            else
                dp[i] = dp[i-1];
        }
        return dp[s.length()];
    }
}

剑指 Offer 47. 礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

思路：
深度优先搜索。要用记忆化，不然内存超限。

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        return dfs(m - 1, n - 1, new int[m][n], grid);
    }

    private int dfs(int i, int j, int[][] cache, int[][] grid) {
        if (i < 0 || j < 0) {
            return Integer.MIN_VALUE;
        }
        if (i == 0 && j == 0) {
            return grid[i][j];
        }
        if (cache[i][j] != 0) {
            return cache[i][j];
        }
        int sum = Math.max(dfs(i - 1, j, cache, grid), dfs(i, j - 1, cache, grid));
        cache[i][j] = sum + grid[i][j];
        return cache[i][j];
    }
}

思路2：
动态规划。
执行用时：3 ms, 在所有 Java 提交中击败了83.17%的用户
内存消耗：42.5 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }
}

剑指 Offer 60. n个骰子的点数

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

思路：
动态规划。
1.表示状态
dp[i][j]，表示投掷完 i 枚骰子后，点数 j 的出现次数。
2.找出状态转移方程
第 n 枚骰子，它的点数可能为 1 , 2, 3, … , 6，因此投掷完 n 枚骰子后点数 j 出现的次数，可以由投掷完 n−1 枚骰子后，对应点数 j-1, j-2, j-3, … , j-6 出现的次数之和转化过来。
3.边界处理
把直接知道的状态初始化就好了。我们可以直接知道的状态是第一阶段的状态：投掷完 11 枚骰子后，它的可能点数分别为 1, 2, 3, … , 61,2,3,…,6 ，并且每个点数出现的次数都是 11。
返回结果的数组长度为 5n+1。
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：37.6 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public double[] twoSum(int n) {
        int[][] dp = new int[15][70];

        for (int i = 1; i <= 6; i++) {
            dp[1][i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = i; j <= 6 * i; j++) {
                for (int k = 1; k <= 6; k++) {
                    if (j - k < 0) {
                        break;
                    }
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }

        int all = (int) Math.pow(6, n), index = 0;
        double[] res = new double[5 * n + 1];
        for (int i = n; i <= 6 * n; i++) {
            res[index++] = dp[n][i] * 1.0 / all;
        }
        return res;
    }
}

剑指 Offer 63. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

思路：
动态规划。详见LeetCode记录中的股票问题专题。
执行用时：4 ms, 在所有 Java 提交中击败了15.43%的用户
内存消耗：39.9 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }
        int[][] dp = new int[len][2];
        dp[0][0] = 0; // 持现金
        dp[0][1] = -prices[0]; // 持股票
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
        return dp[len - 1][0];
    }
}

面试

塔圆柱问题

给定n个空心圆柱体（内半径 r，厚度 s，高度 h），将他们搭起来最大能到达到多高。如果 rj+sj>=ri+ri 并且 ri+si>=rj 才能将木头i放到木头j上面。
sample input:
3
1 2 3
2 2 3
5 1 2
output:
6

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;


public class Other动规_圆柱体问题 {

    static int N,H;//圆柱体的个数和高度
    static cylinder[] a;
    static cylinder below;
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner reader=new Scanner(System.in);
        N=reader.nextInt();
        a=new cylinder[N];
        below=new cylinder(0, 1<<30, 0);//将底下的圆柱体初始为内半径为0，厚度为无穷大，高度为0。
        H=0;//将高度初始化为0
        //读取N个圆柱体的规模
        for(int j=0;j<N;j++) {
            int r=reader.nextInt();
            int s=reader.nextInt();
            int h=reader.nextInt();
            a[j]=new cylinder(r, s, h);
        }
        //在算法中切记不要自己的写例如冒泡排序快速排序等算法，用这个方法不容易出错。
        List<cylinder> aList=new ArrayList<cylinder>(Arrays.asList(a));//该方法是将数组转化为list,但是注意原数组却不会发生变化
        Collections.sort(aList);
        int c=0;
        for( cylinder e: aList) {
            System.out.println(e.toString());//验证排序正确与否，可以去掉
            a[c++]=e;
        }

        int maxH=0;
        for(int i=0;i<N;i++) {
            H=f(i);
            System.out.println(i+" "+H);//验证递归选择的结果，可以去掉
            maxH=Math.max(maxH, H);
            H=0;
            below.r=0;
            below.s=1<<30;
        }
        System.out.println(maxH);
    }
    //一个拥有自定义排序的类
    static class cylinder implements Comparable<cylinder>{
        private int r;
        private int s;
        private int h;
        public cylinder(int r,int s,int h) {
            this.r=r;
            this.s=s;
            this.h=h;
        }
        public int getR() {
            return r;
        }
        public int getS() {
            return s;
        }
        public int getH() {
            return h;
        }
        //实现Comparable接口，重写接口方法
        //如果指定的数与参数相等返回0；如果指定的数外半径小于参数返回 -1；
        //如果指定的数外半径大于参数返回 1,执行交换，此时升序排序，倒序情况则相反。
        @Override
        public int compareTo(cylinder next) {
            return (this.r+this.s)-(next.getR()+next.getS());            
        }    
        @Override
        public String toString() {
            return "r="+r+",s="+s+",h="+h+"。";
        }

    }
    static int f(int n) {
        if(n<0)
            return H;
        if(a[n].r+a[n].s<=below.r+below.s&&a[n].r+a[n].s>=below.r) {
            H+=a[n].h;
            below.r=a[n].r;
            below.s=a[n].s;
        }
        return f(n-1);
    }

}

2. 动态规划问题汇总

LeetCode

区间 DP

字符串匹配问题

树形 DP

计数型 DP

62. 不同路径（√）

63. 不同路径 II（√）

递推型 DP

70. 爬楼梯（√）

509. 斐波那契数（√）

概率型 DP

博弈型 DP

1、翻转游戏

2、Nim游戏

3、石子游戏

记忆化搜索

剑指 Offer

面试

塔圆柱问题