2.动态规划（二）

2020-06-13 本文已影响0人今天柚稚了么

https://leetcode-cn.com/tag/dynamic-programming/

题目汇总

85. 最大矩形困难（先做 84. 柱状图中最大的矩形，85更难，不会做）

87. 扰乱字符串困难（？？？）没做

91. 解码方法中等

95. 不同的二叉搜索树 II中等（大致能看懂）

96. 不同的二叉搜索树中等藕（我是谁我在哪？？？）

97. 交错字符串困难（没做）

115. 不同的子序列困难（可看题解做出）

120. 三角形最小路径和中等[✔]

121. 买卖股票的最佳时机简单

123. 买卖股票的最佳时机 III困难※※

85. 最大矩形困难

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6

87. 扰乱字符串困难

给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。
下图是字符串 s1 = "great" 的一种可能的表示形式。

在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。
例如，如果我们挑选非叶节点 "gr" ，交换它的两个子节点，将会产生扰乱字符串 "rgeat" 。

我们将 "rgeat” 称作 "great" 的一个扰乱字符串。
给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。
示例 1: 输入: s1 = "great", s2 = "rgeat"，输出: true
示例 2: 输入: s1 = "abcde", s2 = "caebd"，输出: false

91. 解码方法中等

一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1，'B' -> 2，...，'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

思路：动态规划

当前位为0时，必须和前一位结合进行解码；
当前位为1-9时，可以单独解码，也可以和前一位结合解码。
动态转移方程好想出来，边界条件的处理很难想的全面。

class Solution {
    public int numDecodings(String s) {
        int len = s.length();
        if(s.charAt(0) == '0') 
            return 0;
        if(len <= 1)
            return len;
        
        int[] dp = new int[len];
        dp[0] = 1;
        //没考虑到这两种情况
        for(int i=1;i<len;i++){
            //比如100
            if(s.charAt(i-1) == '0' && s.charAt(i) == '0'){
                return 0;
            }
            //比如30
            if(s.charAt(i-1) > '2' && s.charAt(i) == '0'){
                return 0;
            }
        }
        int sum = (s.charAt(0)-48)*10+(s.charAt(1)-48);//用前两位来计算dp[1]
        if(sum >= 11 && sum <= 26 && sum!= 20){
            dp[1] = 2;
        }else{
            dp[1] = 1;
        }
        for(int i=2;i<len;i++){
            if(s.charAt(i)=='0'){//如果当前位为0，则必须和前一位结合进行解码
                dp[i] = dp[i-2];
            }else{
                int curSum = (s.charAt(i-1)-48)*10+(s.charAt(i)-48);//转换为数字
                if(curSum >= 11&& curSum <= 26){
                    dp[i] = dp[i-1] + dp[i-2];//和前一位结合解码
                }else{
                    dp[i] = dp[i-1];//单独解码
                }
            }
        }
    return dp[len-1];
    }
}

代码参考https://www.cnblogs.com/wangbobobobo/p/10988909.html

95. 不同的二叉搜索树 II中等(不会做）

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例:
输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

精选题解抄的代码，正在努力看懂中......https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-2-7/

思路一：递归，比较好理解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {//执行用时 :1 ms, 在所有 Java 提交中击败了99.94%的用户
        List<TreeNode> ans = new ArrayList<TreeNode>();
        if (n == 0) {
            return ans;
        }
        return getAns(1, n);
    }
    private List<TreeNode> getAns(int start, int end) { 
        List<TreeNode> ans = new ArrayList<TreeNode>();
        //此时没有数字，将 null 加入结果中
        if (start > end) {
            ans.add(null);
            return ans;
        }
        //只有一个数字，当前数字作为一棵树加入结果中
        if (start == end) {
            TreeNode tree = new TreeNode(start);
            ans.add(tree);
            return ans;
        }
        //尝试每个数字作为根节点
        for (int i = start; i <= end; i++) {
            //得到所有可能的左子树
            List<TreeNode> leftTrees = getAns(start, i - 1);
            //得到所有可能的右子树
            List<TreeNode> rightTrees = getAns(i + 1, end);
            //左子树右子树两两组合
            for (TreeNode leftTree : leftTrees) {
                for (TreeNode rightTree : rightTrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    //加入到最终结果中
                    ans.add(root);
                }
            }
        }
        return ans;
    }
}

思路二：动态规划

首先我们每次新增加的数字大于之前的所有数字，所以新增加的数字出现的位置只可能是根节点或者是根节点的右孩子，右孩子的右孩子，右孩子的右孩子的右孩子等等，总之一定是右边。其次，新数字所在位置原来的子树，改为当前插入数字的左孩子即可，因为插入数字是最大的。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {//执行用时 :1 ms, 在所有 Java 提交中击败了99.94%的用户
        List<TreeNode> pre = new ArrayList<TreeNode>();
        if (n == 0) {
            return pre;
        }
        pre.add(null);
        //每次增加一个数字
        for (int i = 1; i <= n; i++) {
            List<TreeNode> cur = new ArrayList<TreeNode>();
            //遍历之前的所有解
            for (TreeNode root : pre) {
                //插入到根节点
                TreeNode insert = new TreeNode(i);
                insert.left = root;
                cur.add(insert);
                //插入到右孩子，右孩子的右孩子...最多找 n 次孩子
                for (int j = 0; j <= n; j++) {
                    TreeNode root_copy = treeCopy(root); //复制当前的树
                    TreeNode right = root_copy; //找到要插入右孩子的位置
                    int k = 0;
                    //遍历 j 次找右孩子
                    for (; k < j; k++) {
                        if (right == null)
                            break;
                        right = right.right;
                    }
                    //到达 null 提前结束
                    if (right == null)
                        break;
                    //保存当前右孩子的位置的子树作为插入节点的左孩子
                    TreeNode rightTree = right.right;
                    insert = new TreeNode(i);
                    right.right = insert; //右孩子是插入的节点
                    insert.left = rightTree; //插入节点的左孩子更新为插入位置之前的子树
                    //加入结果中
                    cur.add(root_copy);
                }
            }
            pre = cur;

        }
        return pre;
    }


    private TreeNode treeCopy(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode newRoot = new TreeNode(root.val);
        newRoot.left = treeCopy(root.left);
        newRoot.right = treeCopy(root.right);
        return newRoot;
    }
}

96. 不同的二叉搜索树中等

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

思路：动态规划

抄自题解https://leetcode-cn.com/problems/unique-binary-search-trees/solution/cdong-tai-gui-hua-zhu-bu-fen-xi-zhuang-tai-zhuan-y/
动态规划分析
在已知前n-1个数的二叉搜索树数目后，插入第n个数，有哪些情况？
1.第n个数做根节点，前n-1个数形成其左子树，右子树为0个数，dp[n-1]×dp[0]种
2.第n-1个数做根节点，左子树为前n-2个数，右子树为第n个数，dp[n-2]×dp[1]种
...
n-i+1.第i个数做根节点，左子树为前i-1个数，右子树为后n-i个数，dp[i-1]×dp[n-i]种
...
n.第1个数做根节点，左子树为0个数，右子树为后n-1个数，dp[0]×dp[n-1]种
我们将所有情况的二叉搜索树加起来即可
技巧：不妨初始化dp[0]=1,则可顺利循环解决

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for(int i=1;i<=n;i++){// 从1...n的二叉搜索数数目
            for(int j=1;j<=i;j++){// 逐步选用1...n作为根节点
                dp[i] += dp[j - 1] * dp[i - j];// 左侧j-1个数，右侧i-j个数
            }
        }
    return dp[n];
    }
}

97. 交错字符串困难

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

115. 不同的子序列困难

给定一个字符串 S和一个字符串 T，计算在 S 的子序列中 T 出现的个数。
一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。
示例 1：
输入：S = "rabbbit", T = "rabbit"，输出：3
解释：
如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

思路：动态规划

评论区Ant解释了状态转移方程，这里搬运他的回答如下：
1：为啥状态方程这样对？ 2：怎么想到这样的状态方程？
我个人习惯dp[i][j] 表示为s[0-i] 和t[0-j]均闭区间的子序列个数，但这样不能表示s和t空串的情况
所以声明 int[][] dp = new int[m + 1][n + 1]; 这样dp[0][x]可以表示s为空串，dp[x][0]同理。
先不扣初始化的细节，假设dp[i][j] 就是s[i] 和t[j] 索引的元素子序列数量
1：为啥状态方程是： s[i] == t[j] 时 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
s[i] != t[j] 时 dp[i][j] = dp[i-1][j]
先看s[i] == t[j] 时，以s = "rara" t = "ra" 为例，当i = 3, j = 1时，s[i] == t[j]。
此时分为2种情况，用最后一位的a + 不用最后一位的a。
如果用s串最后一位的a,那么t串最后一位的a也被消耗掉，此时的子序列其实=dp[i-1][j-1]
如果不用s串最后一位的a，那就得看"rar"里面是否有"ra"子序列的了，就是dp[i-1][j]
所以 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
再看s[i] != t[j] 比如 s = "rarb" t = "ra" 还是当i = 3, j = 1时，s[i] != t[j]
此时显然最后的b想用也用不上啊。所以只能指望前面的"rar"里面是否有能匹配"ra"的
所以此时dp[i][j] = dp[i-1][j]
2: 怎么想到这样状态方程的？
一点个人经验，见过的很多2个串的题，大部分都是dp[i][j] 分别表示s串[0...i] 和t串[0...j]怎么怎么样然后都是观察s[i]和t[j]分等或者不等的情况而且方程通常就是 dp[i-1][j-1] 要么+ 要么 || dp[i-1][j]类似的
类似的题比如有 10：正则表达式匹配 44：通配符匹配编辑距离 1143：最长公共子序列等等的还有几道想不起来了

class Solution {//执行用时 :8 ms, 在所有 Java 提交中击败了80.13%的用户
    public int numDistinct(String s, String t) {
        int slen = s.length();
        int tlen = t.length();
        int[][] dp = new int[slen + 1][tlen + 1];//dp[i][j]表示从s[0,i]中能选出多少个t[0,j]
        for(int i=0;i<slen;i++){
            dp[i][0] = 1;// t 是空串
        }
        for(int i=1;i<=slen;i++){
            for(int j=1;j<=tlen;j++){
                if(s.charAt(i - 1) == t.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
    return dp[slen][tlen];
    }
}

120. 三角形最小路径和中等

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：

自顶向下的最小路径和为 11（即，2 + 3+ 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

思路：动态规划

自底向上，从倒数第二行开始计算每个数字到下一个节点的最小值并加上当前节点值存入当前节点，最后顶点中存储的就是最终的最短路径结果。

class Solution {//执行用时 :3 ms, 在所有 Java 提交中击败了75.45%的用户
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
 
        //dp[i][j]表示包含第i行第j列元素的最小路径和，加1可以不用初始化最后一行
        int[][] dp = new int[triangle.size() + 1][triangle.size() + 1];

        for (int i = triangle.size() - 1; i >= 0; i--) {
            List<Integer> rows = triangle.get(i);
            for (int j = 0; j < rows.size(); j++) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + rows.get(j);
            }
        }
        return dp[0][0];
    }
}

121. 买卖股票的最佳时机简单

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

思路：动态规划

找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。

class Solution {
    public int maxProfit(int[] prices) {//执行用时 :1 ms
        if(prices == null || prices.length <= 1)
            return 0;
        int max = 0;//最大利润
        int min = prices[0];//历史最低价格
        for(int i=0;i<prices.length;i++){
            if(prices[i]<min){
                min = prices[i];
            }
            else if(prices[i]-min>max){
                max = prices[i] - min;
            }     
        }
    return max;
    }
}

123. 买卖股票的最佳时机 III困难※※

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

思路：动态规划

用一个状态转移方程秒杀了 6 道股票买卖问题，看了很久才看懂
出处：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/yi-ge-tong-yong-fang-fa-tuan-mie-6-dao-gu-piao-wen/关键就在于列举出所有可能的「状态」，然后想想怎么穷举更新这些「状态」。一般用一个多维 dp 数组储存这些状态，从 base case 开始向后推进，推进到最后的状态，就是我们想要的答案。

class Solution {
    public int maxProfit(int[] prices) {//执行用时 :6 ms, 在所有 Java 提交中击败了51.40%
        if (prices.length == 0)
            return 0;
        int max_k = 2;
        int[][][] dp = new int[prices.length][max_k + 1][2];
        for (int i = 0; i < prices.length; i++){
            for (int k = max_k; k >= 1; k--) {
                if (i - 1 == -1) { 
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                continue; 
                }
                dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
            }
        }
    return dp[prices.length - 1][max_k][0];      
    }
}

2.动态规划（二）

题目汇总

85. 最大矩形困难（先做 84. 柱状图中最大的矩形，85更难，不会做）

87. 扰乱字符串困难（？？？）没做

91. 解码方法中等

95. 不同的二叉搜索树 II中等（大致能看懂）

96. 不同的二叉搜索树中等藕（我是谁我在哪？？？）

97. 交错字符串困难（没做）

115. 不同的子序列困难（可看题解做出）

120. 三角形最小路径和中等[✔]

121. 买卖股票的最佳时机简单

123. 买卖股票的最佳时机 III困难※※

85. 最大矩形困难

87. 扰乱字符串困难

91. 解码方法中等

思路：动态规划

95. 不同的二叉搜索树 II中等(不会做）

思路一：递归，比较好理解

思路二：动态规划

96. 不同的二叉搜索树中等

思路：动态规划

97. 交错字符串困难

115. 不同的子序列困难

思路：动态规划

120. 三角形最小路径和中等

思路：动态规划

121. 买卖股票的最佳时机简单

思路：动态规划

123. 买卖股票的最佳时机 III困难※※

思路：动态规划

猜你喜欢

热点阅读