网络彩票代理怎么做社区网站,网页版qq邮箱登录,网站富文本的内容怎么做,多语种网站建设开发文章目录 跳台阶 BM63 简单跳台阶扩展 JZ71 简单打家结舍 LC198 中等打家劫舍2 LC213中等最长连续递增序列 LC674 简单乘积最大子数组LC152 中等最长递增子序列LC300 中等最长重复子数组LC718最长公共子串NC BM66最长公共子序列LC1143 中等完全平方数LC279零钱兑换 LC322 中等单… 文章目录 跳台阶 BM63 简单跳台阶扩展 JZ71 简单打家结舍 LC198 中等打家劫舍2 LC213中等最长连续递增序列 LC674 简单乘积最大子数组LC152 中等最长递增子序列LC300 中等最长重复子数组LC718最长公共子串NC BM66最长公共子序列LC1143 中等完全平方数LC279零钱兑换 LC322 中等单词拆分LC139 中等编辑距离LC72 困难买卖股票的最佳时机LC121 简单买卖股票的最佳时机2 LC122中等不同路径LC62 中等最小路径和LC64 中等分割等和子集LC416 中等 跳台阶 BM63 简单
题目链接 代码
public class Solution {public int jumpFloor (int number) {if(number1||number2)return number;// 跳一步或两步else return jumpFloor(number-1) jumpFloor(number-2);}
}跳台阶扩展 JZ71 简单
题目链接 描述 一只青蛙一次可以跳上1级台阶也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。 思路
F(n) F(n-1)F(n-2)F(n-3)…F(1)1F(n-1)F(n-1) 2*F(n-1)F(3)F(2)F(1)1
跳上第3阶台阶可以从第2阶、第1阶跳上去也可以从第0阶直接1步跳上第3阶。
代码1:
public class Solution {// 当前无优化可添加记忆数组优化时间复杂度public int jumpFloorII (int number) {if(number 1) return 1;int count 1;for(int i 1;i number;i){countjumpFloorII(number-i);}return count;}
}代码2:
public class Solution {public int jumpFloorII (int number) {if(number 1) return 1;return 2*jumpFloorII(number-1);}
}打家结舍 LC198 中等
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
示例 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 。代码
class Solution {int[] memory;// 备忘录public int rob(int[] nums) {int len nums.length;memory new int[len];Arrays.fill(memory,-1);// 注意填充-1return DP(nums,0,len-1,0);}// 能打劫的范围[start,end],从i家开始选择是否打劫public int DP(int[] nums,int start,int end,int i){if(iend)return nums[i];if(iend)return 0;if(memory[i]!-1)return memory[i];// 查找备忘录memory[i] Math.max(DP(nums,start,end,i1),// 不选nums[i]DP(nums,start,end,i2) // 选 隔一家在决定选择);return memory[i];}
}打家劫舍2 LC213中等
题目链接
你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。
示例 1输入nums [2,3,2]
输出3
解释你不能先偷窃 1 号房屋金额 2然后偷窃 3 号房屋金额 2, 因为他们是相邻的。
示例 2输入nums [1,2,3,1]
输出4
解释你可以先偷窃 1 号房屋金额 1然后偷窃 3 号房屋金额 3。偷窃到的最高金额 1 3 4 。
示例 3输入nums [1,2,3]
输出3思路1 2 3 4 5围成一圈即1与5不能同时选则可看作是从1 2 3 4里选以及从2 3 4 5里选取两者最大即可。
代码
class Solution {int[] memory;// 备忘录public int rob(int[] nums) {int len nums.length;if(len1)return nums[0];//base case memory new int[len];Arrays.fill(memory,-1);// 注意填充-1int r1 DP(nums,0,len-2,0);Arrays.fill(memory,-1);// 注意填充-1int r2 DP(nums,1,len-1,1);return Math.max(r1,r2);}// 能打劫的范围[start,end],从i家开始选择是否打劫public int DP(int[] nums,int start,int end,int i){if(iend)return nums[i];//baseif(iend)return 0;//baseif(memory[i]!-1)return memory[i];// 查找备忘录memory[i] Math.max(DP(nums,start,end,i1),// 不选nums[i]DP(nums,start,end,i2) // 选 隔一家在决定选择);return memory[i];}
}最长连续递增序列 LC674 简单
题目链接 给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 rl r确定如果对于每个 l i r都有 nums[i] nums[i 1] 那么子序列 [nums[l], nums[l 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1输入nums [1,3,5,4,7]
输出3
解释最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的因为 5 和 7 在原数组里被 4 隔开。
示例 2输入nums [2,2,2,2,2]
输出1
解释最长连续递增序列是 [2], 长度为1。
代码
class Solution {public int findLengthOfLCIS(int[] nums) {if(nums.length1)return 1;int finalresult 0;// 以下标 i为结尾的数组的连续递增的子序列长度为 dp[i]int[] dp new int[nums.length]; Arrays.fill(dp,1);for(int i 1; i nums.length;i){if(nums[i-1]nums[i]){dp[i] dp[i-1]1;}finalresult Math.max(finalresult, dp[i]);}return finalresult;}
}或
class Solution {public int findLengthOfLCIS(int[] nums) {if(nums.length1)return 1;int finalresult 0;int temresult 1;for(int i 0; i nums.length-1;i){if(nums[i]nums[i1]){temresult;}else{temresult1;}finalresult Math.max(finalresult,temresult);}return finalresult;}
}乘积最大子数组LC152 中等
题目链接
给你一个整数数组 nums 请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例 1:输入: nums [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:输入: nums [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。代码
class Solution {public int maxProduct(int[] nums) {int len nums.length;// 因为nums中存在负数乘积最小的值乘以-1可能变为乘积最大int[] dpmin new int[len];// 以i结尾的乘积最小子数组的乘积int[] dpmax new int[len];// 以i结尾的乘积最大子数组的乘积dpmin[0] nums[0];dpmax[0] nums[0];for(int i 1; i len; i){dpmin[i] min(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i],nums[i]);dpmax[i] max(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i],nums[i]);}int result dpmax[0];for(int r1:dpmax){result resultr1?r1:result;} return result;}int max(int i,int j,int k){return Math.max(i,Math.max(j,k));}int min(int i,int j,int k){return Math.min(i,Math.min(j,k));}
}最长递增子序列LC300 中等
题目链接 给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1
输入nums [10,9,2,5,3,7,101,18] 输出4 解释最长递增子序列是 [2,3,7,101]因此长度为 4 。 示例 2
输入nums [0,1,0,3,2,3] 输出4 示例 3
输入nums [7,7,7,7,7,7,7] 输出1
代码
class Solution {public int lengthOfLIS(int[] nums) {int len nums.length;int res 1;// 以下标 i为结尾的数组的递增的子序列长度为 dp[i]int[] dp new int[len];Arrays.fill(dp,1);for(int i 0; i len;i){for(int j 0;j i;j){if(nums[i]nums[j]){dp[i] Math.max(dp[i],dp[j]1);}}}for(int i 0; i len;i){res Math.max(res,dp[i]);}return res;}
}最长重复子数组LC718
题目链接 给两个整数数组 nums1 和 nums2 返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1
输入nums1 [1,2,3,2,1], nums2 [3,2,1,4,7] 输出3 解释长度最长的公共子数组是 [3,2,1] 。 示例 2
输入nums1 [0,0,0,0,0], nums2 [0,0,0,0,0] 输出5
class Solution {public int findLength(int[] nums1, int[] nums2) {int[][] dp new int[nums1.length1][nums2.length1];int finalresult 0;// 两个数组就是两个forfor(int i 1; i nums1.length; i){ // 从nums1的第1个数字开始for(int j 1; j nums2.length; j){// 从nums2的第1个数字开始if(nums1[i-1]nums2[j-1]){// 如果相同dp[i][j] dp[i-1][j-1]1;}finalresult Math.max(dp[i][j],finalresult);}}return finalresult;}
}最长公共子串NC BM66
题目链接 题目与LC718相似
public class Solution {/*** param str1 string字符串 the string* param str2 string字符串 the string* return string字符串*/public String LCS (String str1, String str2) {// write code hereif(str1.length()0||str2.length()0)return ;int[][] dp new int[str1.length()1][str2.length()1];for(int i 0;i str1.length();i){dp[i][0] 0;}for(int i 0;i str2.length();i){dp[0][i] 0;}String str ;int maxlen 0;for(int i 0; i str1.length();i){for(int j 0; j str2.length();j){if(str1.charAt(i)str2.charAt(j)){dp[i1][j1] dp[i][j]1;if(maxlendp[i1][j1]){maxlen dp[i1][j1];str str1.substring(i-maxlen1,i1);}}}}return str;}
}最长公共子序列LC1143 中等
题目链接 给定两个字符串 text1 和 text2返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 返回 0 。
一个字符串的 子序列 是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。
例如“ace” 是 “abcde” 的子序列但 “aec” 不是 “abcde” 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1输入text1 abcde, text2 ace
输出3
解释最长公共子序列是 ace 它的长度为 3 。
示例 2输入text1 abc, text2 abc
输出3
解释最长公共子序列是 abc 它的长度为 3 。
示例 3输入text1 abc, text2 def
输出0
解释两个字符串没有公共子序列返回 0 。代码
class Solution {public int longestCommonSubsequence(String text1, String text2) {int len1 text1.length();int len2 text2.length();int[][] dp new int[len11][len21];for(int i 0;i len1;i){dp[i][0] 0;}for(int i 0;i len2;i){dp[0][i] 0;}for(int i 1; i len1;i){for(int j 1;j len2;j){if(text1.charAt(i-1)text2.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 dp[len1][len2];}
}完全平方数LC279
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。
示例 1
输入n 12
输出3
解释12 4 4 4示例 2
输入n 13
输出2
解释13 4 9代码
class Solution {public int numSquares(int n) {int[] dp new int[n1];Arrays.fill(dp,Integer.MAX_VALUE);dp[0] 0;for(int i 1; i n;i){for(int j 1; j*j i;j){dp[i] Math.min(dp[i],dp[i-j*j]1);}}return dp[n];}
}零钱兑换 LC322 中等
题目链接 给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1
输入coins [1, 2, 5], amount 11
输出3
解释11 5 5 1示例 2
输入coins [2], amount 3
输出-1示例 3
输入coins [1], amount 0
输出0代码
class Solution {MapInteger,Integer memory new HashMap();public int coinChange(int[] coins, int amount) {return DP(coins,amount);}public int DP(int[] coins,int target){if(target0)return 0;if(target0) return -1;// 查询备忘录if(memory.containsKey(target))return memory.get(target);int result Integer.MAX_VALUE; // 注意此行位置for(int coin:coins){int n DP(coins,target-coin);// 存储备忘录memory.put(target-coin,n);if(n -1) continue; // 注意此行result Math.min(result,n1);}return result Integer.MAX_VALUE?-1:result; // 注意此行}
}单词拆分LC139 中等
题目链接
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。
示例 1
输入: s leetcode, wordDict [leet, code]
输出: true
解释: 返回 true 因为 leetcode 可以由 leet 和 code 拼接成。示例 2
输入: s applepenapple, wordDict [apple, pen]
输出: true
解释: 返回 true 因为 applepenapple 可以由 apple pen apple 拼接成。注意你可以重复使用字典中的单词。示例 3
输入: s catsandog, wordDict [cats, dog, sand, and, cat]
输出: false提示
1 s.length 300
1 wordDict.length 1000
1 wordDict[i].length 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同方法1遍历所有单词的长度查看是否匹配
class Solution {ListString wordDict;int[] memory ;public boolean wordBreak(String s, ListString wordDict1) {wordDict wordDict1;memory new int[s.length()1];Arrays.fill(memory,-2);return DP(s,0);}boolean DP(String s,int i){if(is.length()){return true;}if(is.length()){return false;}if(memory[i]!-2)return memory[i]1?true:false;for(String word:wordDict){int len word.length();if(ilens.length())continue;if(s.substring(i,ilen).equals(word)){boolean r1 DP(s,ilen);if(r1true){memory[i]1;return true;}}}memory[i]0;return false;}
}方法2遍历所有长度查看是否匹配
class Solution {ListString wordDict1;int[] memory;public boolean wordBreak(String s, ListString wordDict) {wordDict1 wordDict;memory new int[s.length()];Arrays.fill(memory,-1);return DP(s,0);}public boolean DP(String s,int i ){if(i s.length())return true;if(memory[i]!-1)return memory[i]1?true:false;for (int slen 1; slen i s.length(); slen) {String s1 s.substring(i,i slen);if(wordDict1.contains(s1)){boolean b DP(s, i slen);if(b true){memory[i] 1;return true;}}}memory[i] 0;return false;}
}编辑距离LC72 困难
题目链接
给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符
示例 1
输入word1 horse, word2 ros
输出3解释
horse - rorse (将 h 替换为 r)
rorse - rose (删除 r)
rose - ros (删除 e)示例 2
输入word1 intention, word2 execution
输出5解释
intention - inention (删除 t)
inention - enention (将 i 替换为 e)
enention - exention (将 n 替换为 x)
exention - exection (将 n 替换为 c)
exection - execution (插入 u)思路 代码
class Solution {int[][] memory;public int minDistance(String word1, String word2) {memory new int[word1.length()][word2.length()];for(int[] m:memory){Arrays.fill(m,-1);}return DP(word1,word1.length()-1,word2,word2.length()-1);}public int DP(String w1,int i,String w2,int j){if(i -1) return j1;if(j -1) return i1;if(memory[i][j]!-1)return memory[i][j];if(w1.charAt(i) w2.charAt(j)){int r DP(w1,i-1,w2,j-1);memory[i][j] r;return r;}else{int r min(DP(w1,i ,w2,j-1), // 插入:在w1的i的位置插入j被匹配j-1DP(w1,i-1,w2,j ), // 删除:对w1的i的位置删除i-1j未匹配DP(w1,i-1,w2,j-1) // 替换:对w1的i的位置替换j被匹配i替换后被匹配) 1;memory[i][j] r;return r;}}int min(int i,int j,int x){return Math.min(i,Math.min(j,x));}
}买卖股票的最佳时机LC121 简单
题目链接
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。
示例 1
输入[7,1,5,3,6,4]
输出5
解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。示例 2
输入prices [7,6,4,3,1]
输出0
解释在这种情况下, 没有交易完成, 所以最大利润为 0。设置一个二期数组dp[][]第一维表示天数第二维表示是否持有股票。
class Solution {public int maxProfit(int[] prices) {int[][] dp new int[prices.length][2]; // dp[i][1/0]:第i天持有1/不持有0for(int i 0; i prices.length;i){if(i-1-1){dp[i][0] 0;dp[i][1] -prices[0];continue;}// 未持有股票max昨天未持有股票昨天持有股票今天卖出dp[i][0] Math.max(dp[i-1][0],dp[i-1][1]prices[i]);// 持有股票max昨天持有股票昨天未股票今天买入dp[i][1] Math.max(dp[i-1][1],-prices[i]);// 只能买一次所以第一次买时所赚利润为0-price。}return dp[prices.length-1][0];}
}买卖股票的最佳时机2 LC122中等
题目链接
给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。
在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1
输入prices [7,1,5,3,6,4]
输出7
解释在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4 。随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3 。总利润为 4 3 7 。示例 2
输入prices [1,2,3,4,5]
输出4
解释在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4 。总利润为 4 。示例 3
输入prices [7,6,4,3,1]
输出0
解释在这种情况下, 交易无法获得正利润所以不参与交易可以获得最大利润最大利润为 0 。
代码
class Solution {public int maxProfit(int[] prices) {int[][] dp new int[prices.length][2];for(int i 0; i prices.length;i){if(i-1-1){dp[i][0] 0;dp[i][1] -prices[0];continue;}dp[i][0]Math.max(dp[i-1][0],dp[i-1][1]prices[i]);dp[i][1]Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);}return dp[prices.length-1][0];}
}不同路径LC62 中等
题目链接
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。 问总共有多少条不同的路径
示例 1
输入m 3, n 7
输出28示例 2
输入m 3, n 2
输出3
解释
从左上角开始总共有 3 条路径可以到达右下角。
1. 向右 - 向下 - 向下
2. 向下 - 向下 - 向右
3. 向下 - 向右 - 向下示例 3
输入m 7, n 3
输出28示例 4
输入m 3, n 3
输出6代码
class Solution {public int uniquePaths(int m, int n) {int[][] dp new int[m][n];for(int i 0;i m; i){for(int j 0; j n; j){if(i0||j0){dp[i][j] 1;continue;}dp[i][j] dp[i][j-1] dp[i-1][j];}}return dp[m-1][n-1];}最小路径和LC64 中等
题目链接
给定一个包含非负整数的 m x n 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。
说明每次只能向下或者向右移动一步。 代码
class Solution {public int minPathSum(int[][] grid) {int m grid.length;int n grid[0].length;int[][] dp new int[m][n];// base case 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 i 1;i n;i){dp[0][i] dp[0][i-1]grid[0][i];}for(int i 1;i m; i){for(int j 1; j n; j){dp[i][j] Math.min(dp[i-1][j],dp[i][j-1]) grid[i][j];}}return dp[m-1][n-1];}
}分割等和子集LC416 中等
题目链接
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。
示例 1
输入nums [1,5,11,5]
输出true
解释数组可以分割成 [1, 5, 5] 和 [11] 。示例 2
输入nums [1,2,3,5]
输出false
解释数组不能分割成两个元素和相等的子集。题解labuladong的算法笔记
/**引用Labuladong《算法小抄》 的第 192 页。对于这个问题我们可以先对集合求和得出 sum然后把问题转化为背包问题
给一个可装载重量为 sum / 2 的背包和 N 个物品每个物品的重量为 nums[i]。现在让你装物品是否存在一种装法能够恰好将背包装满
第一步要明确两点「状态」和「选择」状态就是「背包的容量」和「可选择的物品」选择就是「装进背包」或者「不装进背包」。
dp 数组的定义dp[i][j] x 表示对于前 i 个物品当前背包的容量为 j 时若 x 为 true则说明可以恰好将背包装满若 x 为 false则说明不能恰好将背包装满。
根据 dp 数组含义可以根据「选择」对 dp[i][j] 得到以下状态转移
如果不把 nums[i] 算入子集或者说你不把这第 i 个物品装入背包那么是否能够恰好装满背包取决于上一个状态 dp[i-1][j]继承之前的结果。
如果把 nums[i] 算入子集或者说你把这第 i 个物品装入了背包那么是否能够恰好装满背包取决于状态 dp[i-1][j-nums[i-1]]*/class Solution {public boolean canPartition(int[] nums) {int sum 0; // 数组一半的大小for(int n:nums){sumn;}if(sum%2!0)return false;sum sum/2;boolean[][] dp new boolean[nums.length1][sum1];// dp[i][j] 前i个物品j大小的包恰好能装满即为true// base casefor(int i 0;i nums.length;i){dp[i][0] true;}for(int i 1; i nums.length;i){for(int j 1; j sum; j){if(j-nums[i-1]0){ // 第i个物品装不下dp[i][j] dp[i-1][j];}else{ // 能装下dp[i][j] dp[i-1][j] || dp[i-1][j-nums[i-1]]; // 装 or 不装}}}return dp[nums.length][sum];}
}参考 Labuladong 代码随想录 力扣DP题库 牛客面试必刷
