心得技巧
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧

[leetcode刷题]——动态规划Ⅱ

发布时间：2022-07-05 发布网站：脚本宝典
脚本宝典收集整理的这篇文章主要介绍了[leetcode刷题]——动态规划Ⅱ，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

　　这篇博客主要记录动态规划中0-1背包问题、股票交易问题和字符串编辑问题

 

一、0-1背包问题

　　

[leetcode刷题]——动态规划Ⅱ

 

 

[leetcode刷题]——动态规划Ⅱ

 

 

 　　416.分割等和子集  （medium） 2021-09-15

　　给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

　　

　　这个题有点难以联想到是背包问题，与背包的惯性思维装取价值最大的物体的问题不同，这个题的恰好装上sum / 2 价值的物体。

还有一点特殊的是，不要被背包问题中的容量、价值、体积限制住思维。这个题中虽然是总价值是 sum / 2, 但是我们定义的时候定义的是背包的总体积是sum / 2, 定义的dp 是能不能将当前的背包恰好装满。

 

class Solution {
    public boolean canPartITion(int[] nums) {
        int sum = computeArraySum(nums);
        if(sum % 2 != 0) return false;
        int W = sum / 2;
        //总体积为W的背包，容量为数组长度，dp表示能填满当前体积的背包
        boolean[] dp = new boolean[W + 1];
        dp[0] = true;
        for(int num : nums){
            for(int i = W; i >= num; i--){
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[W];    
    }
    public int computeArraySum(int[] nums){
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        return sum;
    }
}

 

494.目标和  （medium ）2021-09-15

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

　　这个题与上题类似

　　

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //转换为0-1背包问题，使背包的体积恰好等于(sum + target) / 2 ,这部分取正，另一部分取负
        target = Math.abs(target);
        int sum = computeArraySum(nums);
        if(sum < target || (sum + target) % 2 != 0){
            return 0;
        }
        int w = (sum + target) / 2;
        int[] dp = new int[w + 1];
        dp[0] = 1;
        for(int num : nums){
            for(int i = w; i >= num; i--){
                dp[i] = dp[i] + dp[i - num];
            }
        }
        return dp[w];
        
    }
    
    public int computeArraySum(int[] nums){
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        return sum;
    }
}

 　　同样可以使用 DFs 方法

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //dfs
        return findSubWays(nums, target, 0);

    }

    public int findSubWays(int[] nums, int target, int start){
        if(start == nums.length){
            if(target == 0){
                return 1;
            }else{
                return 0;
            }
        }
        return findSubWays(nums, target - nums[start], start + 1) + 
               findSubWays(nums, target + nums[start], start + 1);
    }
}

 

474.一和零  （medium） 2021-09-22

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

 

public int findMaxForm(String[] strs, int m, int n) {
        if(strs == null || strs.length == 0){
            return 0;
        }
        int[][] dp = new int[m + 1][n + 1];
        for(String s : strs){
            int ones = 0, zeros = 0;
            for(char c : s.toCharArray()){
                if(c == '0'){
                    zeros++;
                }else{
                    ones++;
                }
            }
            for(int i = m; i >= zeros; i--){
                for(int j = n; j >= ones; j--){
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }
        return dp[m][n];
    }

 

322.零钱兑换 （medium) 2021-09-22

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

　　注意，这个题属于完全背包问题。

public int coinChange(int[] coins, int amount) {
        if(coins == null || amount == 0){
            return 0;
        }
        int[] dp = new int[amount + 1];
        for(int coin : coins){
            for(int i = coin; i <= amount; i++){
                if(i == coin){
                    dp[i] = 1;
                }else if(dp[i] == 0 && dp[i - coin] != 0){
                    dp[i] = dp[i - coin] + 1;
                }else if(dp[i - coin] != 0){
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == 0 ? -1 : dp[amount];
    }

 

518. 零钱兑换Ⅱ （medium） 2021-09-22

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

public int change(int amount, int[] coins) {
        if(coins == null){
            return 0;
        }
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int coin : coins){
            for(int i = coin; i <= amount; i++){
                dp[i] = dp[i] + dp[i - coin];
            } 
        }
        return dp[amount];
    }

 

 

139. 单词拆分 （medium） 2021-09-22

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。

　　

public boolean wordbreak(String s, List<String> wordDict) {
        //完全背包问题
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for(int i = 0; i <= len; i++){
            for(String word : wordDict){
                int l = word.length();
                if(i >= l && word.equals(s.substring(i - l , i))){
                    dp[i] = dp[i] | dp[i - l];
                }
            }
        }
        return dp[len];
    }

 

377.数组总和 （medium） 2021-09-22

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

 

public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = 1; i <= target; i++){
            for(int num : nums){
                if(i >= num){
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }

 

二、股票交易问题

 309. 最佳买卖股票时机含冷冻期 （medium）2021-09-22

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

　　代码不是关键，关键在于分析问题，将问题拆解成为两种状态，持有和不持有股票，然后寻找递推表达式

public int maxPRofit(int[] prices) {
        //设置两个状态，持有和不持有股票
        int len = prices.length;
        int[] have = new int[len];
        int[] no = new int[len];
        have[0] = -prices[0];
        for(int i = 1; i < len; i++){
            have[i] = Math.max(have[i - 1], (i > 2 ? no[i - 2] : 0) - prices[i]);
            no[i] = Math.max(no[i - 1], have[i - 1] + prices[i]);
        }
        return no[len - 1];    
    }

 

714. 买卖股票的最佳时机含手续费 （medium） 2021-09-22

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费

 

public int maxprofit(int[] prices, int fee) {
        int len = prices.length;
        int[] hava = new int[len];
        int[] no = new int[len];
        hava[0] = -prices[0];
        for(int i = 1; i < len; i++){
            hava[i] = Math.max(hava[i - 1], no[i - 1] - prices[i]);
            no[i] = Math.max(hava[i - 1] + prices[i] - fee, no[i - 1]);
        }
        return no[len - 1];
    }

 

123. 买卖股票的最佳时机Ⅲ（hard） 2021-09-24

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

 

class Solution {
    public int maxProfit(int[] prices) {
        /**
        对于任意一天考虑四个变量
        fstBuy,在该天第一次买入股票可获得的最大收益
        fstSell, 在该天第一次卖出股票可获得的最大收益
        secBuy, 在该天第二次买入股票可获得的最大收益
        secSell, 在该天第二次卖出股票可获得的最大收益
        分别对四个变量进行相应的更新，最后secSell就是最大
        收益值 （secSell >= fstSell）
         */
        int fstBuy = Integer.MIN_VALUE, fstSell = 0;
        int secBuy = Integer.MIN_VALUE, secSell = 0;
        for(int p : prices){
            fstBuy = Math.max(fstBuy, -p);
            fstSell = Math.max(fstSell, fstBuy + p);
            secBuy = Math.max(secBuy, fstSell - p);
            secSell = Math.max(secSell, secBuy  + p);
        }
        return secSell; 
    }
}

 

188. 买卖股票的最佳时机Ⅳ （hard）2021-09-24

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(k < 1) return 0;
        if(k >= prices.length / 2) return greedy(prices);
        int[][] t = new int[k][2];
        for(int i = 0; i < k; i++){
            t[i][0] = Integer.MIN_VALUE;
        }
        // 0 有持有股票， 1是不持有股票
        for(int p : prices){
            t[0][0] = Math.max(t[0][0], -p);
            t[0][1] = Math.max(t[0][1], t[0][0] + p);
            for(int i = 1; i < k; i++){
                t[i][0] = Math.max(t[i][0], t[i - 1][1] - p);
                t[i][1] = Math.max(t[i][1], t[i][0] + p);
            }
        }
        return t[k - 1][1];
    }
    private int greedy(int[] prices){
        int max = 0;
        for(int i = 1; i < prices.length; i++){
            if(prices[i] - prices[i - 1] > 0){
                max += prices[i] - prices[i - 1];
            }
        }
        return max;
    }
}

 

 

三、字符串编辑

583 .两个字符串的删除操作 （medium） 2021-09-24

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

public int minDistance(String word1, String word2) {
        int l1 = word1.length();
        int l2 = word2.length();
        int[][] dp = new int[l1 + 1][l2 + 1];
        for(int i = 1; i <= l1; i++){
            for(int j = 1; j <= l2; j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return l1 + l2 -  2 * dp[l1][l2];
    }

 

72. 编辑距离 （hard）2021-09-24

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符删除一个字符替换一个字符

 

public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1]; //表示word1 和word2 前i, j 个字母转换所使用的最少操作
        for(int i = 0; i <= m; i++){
            dp[i][0] = i;
        }
        for(int j = 0; j <= n; j++){
            dp[0][j] = j;
        }
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

 

650. 只有两个键的键盘 （medium）2021-09-24

最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：

Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。Paste（粘贴）：粘贴 上一次 复制的字符。给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。

 

public int minSteps(int n) {
        int res = 0;
        for(int i = 2; i <= n; i++){
            while(n % i == 0){
                res += i;
                n /= i;
            }
        }
        return res;
    }

 

脚本宝典总结

以上是脚本宝典为你收集整理的[leetcode刷题]——动态规划Ⅱ全部内容，希望文章能够帮你解决[leetcode刷题]——动态规划Ⅱ所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
标签：javalistloadloadpartitionphppythonStringwhilewhile程序员程序员算法算法
猜你在找的心得技巧相关文章
其他相关热搜词更多
phpjavapython程序员loadpost-format-gallerydivString参数开发ListcapMapClass工具安装SQL数据库资源this
全站导航更多
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧JavaScriptASP.NETPHP编程正则表达式AJAX相关ASP编程JSP编程编程10000问CSS/HTMLFlexvbsDOS/BAThtahtcpythonperl游戏相关VBA远程脚本ColdFusionMsSqlMysqlmariadboracleDB2mssql2008mssql2005SQLitePostgreSQLMongoDB星外虚拟主机华众虚拟主机Linuxwin服务器FTP服务器DNS服务器Tomcatnginxzabbix云和虚拟化bios系统安装系统系统进程Windows系列LINUXRedHat/CentosUbuntu/DebianFedoraSolaris红旗Linux建站经验微信营销网站优化网站策划网络赚钱网络创业站长故事alexa域名photoshop教程摄影教程Fireworks教程CorelDraw教程Illustrator教程Painter教程Freehand教程IndesignSketch笔记本主板内存CPU存储显卡显示器光存储鼠标键盘平板电脑安全教程杀毒防毒安全设置病毒查杀脚本攻防入侵防御工具使用业界动态Exploit漏洞分析
最新心得技巧教程
热门心得技巧教程