2023年8月1日发(作者：)

LeetCode动态规划刷题记录（⼀）背包问题最近在刷LeetCode上的动态规划题⽬，这⾥主要整理⼀下⼀些题⽬的做法，说到动态规划，最典型是的背包问题，让我们⾸先来解决背包问题。问题背景背包问题的背景是有⼀个空间有限的背包（设空间为W）和⼀堆物品，每个物品都有两个属性，⼀个是占据的空间记为w，另⼀个属性是物品的价值v，我们要解决的问题就是在有限的空间W内，将物品装⼊背包，并且使总价值尽可能的⼤。背包问题按⼤类分为三⼤类，⼀、01背包。⼆、多重背包。三完全背包。最常见的问题问法有求⽅案数，求最优⽅案数，求最⼤价值，求能不能满⾜某⼀条件等等。接下来让我们先分别来看看这些问题的原型。01背包01背包是指背包的物品个数都为1，也就是只能使⽤⼀次。这类背包问题我们⾸先要建⽴⼀个⼆维数组dp，其中dp[i][j]表⽰ 前i件物品在体积不超过j的前提下的最⼤价值。其中对于每⼀件物品的体积我们⽤⼀维数组w来存储，对于每个物品的价值⽤⼀维数组v来存储。对于⼀个物品可以有两个状态，⼀个是添加到背包，⼆是没有添加到背包，两种情况需要满⾜以下条件：第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最⼤价值就是总体积不超过 j 的前 i-1 件物品的最⼤价值，即dp[i][j] = dp[i-1][j]。第 i 件物品添加到背包中，直接在前i-1件物品在空间不超过j-w[i]最⼤价值的基础上加上v[i]，即dp[i][j] = dp[i-1][j-w] + v。以上两种情况的选择取决于谁的价值更⼤，⽤公式表⽰就是：dp[i][j]= max(dp[i-1][j],dp[[i-1][j-w]+v)以上公式也就是状态转移⽅程，根据⽅程我们就可以写代码了先上⼀个01背包的模板：public int knapsack(int W, int N, int[] weights, int[] values) { int[][] dp = new int[N + 1][W + 1]; for (int i = 1; i <= N; i++) { int w = weights[i - 1], v = values[i - 1]; for (int j = 1; j <= W; j++) { if (j >= w) { dp[i][j] = (dp[i - 1][j], dp[i - 1][j - w] + v); } else { [i][j] = dp[i - 1][j]; } } }}通过以上⽅程可以看出来前i件物品的状态只和前i-1件物品的状态有关，⽤⼀维的dp数组就可以解决问题，可以将⽅程简化为：dp[j]= max(dp[j],dp[j-w]+v)dp[j-w] 就是 ⼆维数组表⽰的dp[i-1][j-w]，⽽dp[j]则是dp[i-1][j]，这⾥有个⼩问题，在j顺序求解的过程中，dp[i-1][j-w]会被先计算，dp[i-1][j-w]被计算过之后表⽰的就不再是dp[i-1][j]了，⽽是成为了dp[i][j]，⽽在计算后边的dp[j]的时候会⽤到dp[j-w]，⽽此时的dp[j-w]，已经不再是原来的i-1时刻的状态了，所以在计算是会产⽣⼀定的错误，为了解决这⼀问题可以将j来倒序进⾏计算。优化后的代码：public int knapsack(int W, int N, int[] weights, int[] values) { int[] dp = new int[W + 1]; for (int i = 1; i <= N; i++) { int w = weights[i - 1], v = values[i - 1]; for (int j = W; j >= 1; j--) { if (j >= w) { dp[j] = (dp[j], dp[j - w] + v); } } }

return dp[W];}完全背包第⼆类是完全背包，完全背包是指在01背包的基础上，物品的个数可以使⽤任意个没有限制。解决这类问题只要将01背包内循环的代码改成正序就可以了。多重背包第三类是多重背包，多重背包是指在01背包的基础上，物品的个数有限制可以是0-n个。解决这类问题的思路是将其转化成01背包，具体的⽅法就是n个添加同样属性的物品就可以了。常见问题常见的问题有求最优解，求⽅案数，求能不能达成条件等，以下通过具体问题来介绍问题⼀：分割等和⼦集（LeetCode 416）题⽬描述：给定⼀个只包含正整数的⾮空数组。是否可以将这个数组分割成两个⼦集，使得两个⼦集的元素和相等。注意:每个数组中的元素不会超过 100数组的⼤⼩不会超过 200⽰例 1:输⼊: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11].⽰例 2:输⼊: [1, 2, 3, 5]输出: false解释: 数组不能分割成两个元素和相等的⼦集.解题思路：相当于在数组中取出任意数组合使其和等于数组总和的⼀半实现代码class Solution { public boolean canPartition(int[] nums) { int n = ; int sum = 0; for(int i=0;i=nums[i-1]) dp[i][j] = dp[i-1][j]||dp[i-1][j-nums[i-1]]; else dp[i][j] = dp[i-1][j]; } } return dp[][sum/2]; } //空间优化后的代码 public boolean canPartition2(int[] nums) { int n = ; int sum = 0; for(int i=0;i=nums[i-1];j--){ dp[j] = dp[j]||dp[j-nums[i-1]]; } } return dp[sum/2]; }}问题⼆：⽬标和（LeetCode 494）题⽬描述：给定⼀个⾮负整数数组，a1, a2, …, an, 和⼀个⽬标数，S。现在你有两个符号 + 和 -。对于数组中的任意⼀个整数，你都可以从 + 或 -中选择⼀个符号添加在前⾯。返回可以使最终数组和为⽬标数 S 的所有添加符号的⽅法数。⽰例 1:输⼊: nums: [1, 1, 1, 1, 1], S: 3输出: 5解释:-1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3⼀共有5种⽅法让最终⽬标和为3。注意:数组的长度不会超过20，并且数组中的值全为正数。初始的数组的和不会超过1000。保证返回的最终结果为32位整数。解题思路相当于在数组中找出⼀部分数，使其和为(sum+S)/2实现代码class Solution { public int findTargetSumWays(int[] nums, int S) { int n = ; int sum = 0; for(int i = 0 ;i

if(j>=we) dp[i][j]=dp[i-1][j]+dp[i-1][j-we];

else

dp[i][j]=dp[i-1][j];

} } return dp[n][W]; } //空间优化后dp

public int findTargetSumWays2(int[] nums, int S) { int n = ; int sum = 0; for(int i = 0 ;i =we;j--){ dp[j]=dp[j]+dp[j-we]; }

} return dp[W]; }

}问题三：1和 0（LeetCode 474）题⽬描述：在计算机界中，我们总是追求⽤有限的资源获取最⼤的收益。现在，假设你分别⽀配着 m 个 0 和 n 个 1。另外，还有⼀个仅包含 0 和 1 字符串的数组。你的任务是使⽤给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最⼤数量。每个 0 和 1 ⾄多被使⽤⼀次。注意:给定 0 和 1 的数量都不会超过 100。给定字符串数组的长度不会超过 600。⽰例 1:输⼊: Array = {“10”, “0001”, “111001”, “1”, “0”}, m = 5, n = 3输出: 4解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 “10”,“0001”,“1”,“0” 。⽰例 2:输⼊: Array = {“10”, “0”, “1”}, m = 1, n = 1输出: 2解释: 你可以拼出 “10”，但之后就没有剩余数字了。更好的选择是拼出 “0” 和 “1” 。解题思路⼆维dp，多加⼀层循环就可以实现代码class Solution { public int findMaxForm(String[] strs, int m, int n) { if(strs==null||==0) return 0; int [][]dp=new int[m+1][n+1]; for(int i=0;i<;i++){ int ones=0,zeros=0; for(int j=0;j=zeros;j--){ for(int k=n;k>=ones;k--){ dp[j][k]=(dp[j][k],dp[j-zeros][k-ones]+1); } } } return dp[m][n]; }}问题四：零钱兑换（LeetCode 322）题⽬描述：给定不同⾯额的硬币 coins 和⼀个总⾦额 amount。编写⼀个函数来计算可以凑成总⾦额所需的最少的硬币个数。如果没有任何⼀种硬币组合能组成总⾦额，返回 -1。⽰例 1:输⼊: coins = [1, 2, 5], amount = 11输出: 3解释: 11 = 5 + 5 + 1⽰例 2:输⼊: coins = [2], amount = 3输出: -1说明:你可以认为每种硬币的数量是⽆限的。解题思路完全背包，求最优⽅案值实现代码class Solution { public int coinChange(int[] coins, int amount) { if(==0||amount==0) return 0; int n = ; int [] dp = new int [amount+1]; for(int i=1;i<=n;i++){ int w= coins[i-1]; for(int j=w;j<=amount;j++){ if(j==w)//放⼊第⼀个 dp[j]=1; else if(dp[j]==0&&dp[j-w]!=0) dp[j]=dp[j-w]+1; else if(dp[j-w]!=0) dp[j]=(dp[j],dp[j-w]+1); } } return dp[amount]==0?-1:dp[amount]; }}问题五：零钱兑换II（LeetCode518）题⽬描述给定不同⾯额的硬币和⼀个总⾦额。写出函数来计算可以凑成总⾦额的硬币组合数。假设每⼀种⾯额的硬币有⽆限个。⽰例 1:输⼊: amount = 5, coins = [1, 2, 5]输出: 4解释: 有四种⽅式可以凑成总⾦额:5=55=2+2+15=2+1+1+15=1+1+1+1+1⽰例 2:输⼊: amount = 3, coins = [2]输出: 0解释: 只⽤⾯额2的硬币不能凑成总⾦额3。⽰例 3:输⼊: amount = 10, coins = [10]输出: 1注意:你可以假设：0 <= amount (总⾦额) <= 50001 <= coin (硬币⾯额) <= 5000硬币种类不超过 500 种结果符合 32 位符号整数解题思路完全背包求⽅案数问题实现代码class Solution { public int change(int amount, int[] coins) { if(amount==0) return 1; if(coins==null||==0) return 0; int n = ; int [] dp = new int [amount+1]; dp[0]=1; for(int i=1;i<=n;i++){ int w = coins[i-1]; for(int j=w;j<=amount;j++){ dp[j]=dp[j]+dp[j-w]; } } return dp[amount]; }}问题六：单词拆分（LeetCode139）题⽬描述给定⼀个⾮空字符串 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解题思路完全背包问题，有顺序要求，遍历的循环放在⾥边实现代码class Solution { public boolean wordBreak(String s, List wordDict) { int n = (); boolean [] dp = new boolean [n+1]; dp[0]=true; for(int i=1;i<=n;i++){ for(String word:wordDict){//求解顺序完全背包问题对物品的迭代应该放在⾥层 int w = (); if(i>=w&&(ing(i-w,i))){ dp[i]=dp[i]||dp[i-w]; } } } return dp[n]; }}问题七：组合总数IV（LeetCode377）题⽬描述给定⼀个由正整数组成且不存在重复数字的数组，找出和为给定⽬标正整数的组合的个数。⽰例:nums = [1, 2, 3]target = 4所有可能的组合为：(1, 1, 1, 1)(1, 1, 2)(1, 2, 1)(1, 3)(2, 1, 1)(2, 2)(3, 1)请注意，顺序不同的序列被视作不同的组合。因此输出为 7。解题思路完全背包求⽅案数问题实现代码class Solution { public int combinationSum4(int[] nums, int target) { int n = ; int []dp = new int [target+1]; dp[0]=1; for(int i=1;i<=target;i++){ for( int j=1;j<=n;j++){ int w = nums[j-1]; if(i>=w) dp[i]=dp[i]+dp[i-w]; } } return dp[target]; }}

2023年8月1日发(作者：)

LeetCode动态规划刷题记录（⼀）背包问题最近在刷LeetCode上的动态规划题⽬，这⾥主要整理⼀下⼀些题⽬的做法，说到动态规划，最典型是的背包问题，让我们⾸先来解决背包问题。问题背景背包问题的背景是有⼀个空间有限的背包（设空间为W）和⼀堆物品，每个物品都有两个属性，⼀个是占据的空间记为w，另⼀个属性是物品的价值v，我们要解决的问题就是在有限的空间W内，将物品装⼊背包，并且使总价值尽可能的⼤。背包问题按⼤类分为三⼤类，⼀、01背包。⼆、多重背包。三完全背包。最常见的问题问法有求⽅案数，求最优⽅案数，求最⼤价值，求能不能满⾜某⼀条件等等。接下来让我们先分别来看看这些问题的原型。01背包01背包是指背包的物品个数都为1，也就是只能使⽤⼀次。这类背包问题我们⾸先要建⽴⼀个⼆维数组dp，其中dp[i][j]表⽰ 前i件物品在体积不超过j的前提下的最⼤价值。其中对于每⼀件物品的体积我们⽤⼀维数组w来存储，对于每个物品的价值⽤⼀维数组v来存储。对于⼀个物品可以有两个状态，⼀个是添加到背包，⼆是没有添加到背包，两种情况需要满⾜以下条件：第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最⼤价值就是总体积不超过 j 的前 i-1 件物品的最⼤价值，即dp[i][j] = dp[i-1][j]。第 i 件物品添加到背包中，直接在前i-1件物品在空间不超过j-w[i]最⼤价值的基础上加上v[i]，即dp[i][j] = dp[i-1][j-w] + v。以上两种情况的选择取决于谁的价值更⼤，⽤公式表⽰就是：dp[i][j]= max(dp[i-1][j],dp[[i-1][j-w]+v)以上公式也就是状态转移⽅程，根据⽅程我们就可以写代码了先上⼀个01背包的模板：public int knapsack(int W, int N, int[] weights, int[] values) { int[][] dp = new int[N + 1][W + 1]; for (int i = 1; i <= N; i++) { int w = weights[i - 1], v = values[i - 1]; for (int j = 1; j <= W; j++) { if (j >= w) { dp[i][j] = (dp[i - 1][j], dp[i - 1][j - w] + v); } else { [i][j] = dp[i - 1][j]; } } }}通过以上⽅程可以看出来前i件物品的状态只和前i-1件物品的状态有关，⽤⼀维的dp数组就可以解决问题，可以将⽅程简化为：dp[j]= max(dp[j],dp[j-w]+v)dp[j-w] 就是 ⼆维数组表⽰的dp[i-1][j-w]，⽽dp[j]则是dp[i-1][j]，这⾥有个⼩问题，在j顺序求解的过程中，dp[i-1][j-w]会被先计算，dp[i-1][j-w]被计算过之后表⽰的就不再是dp[i-1][j]了，⽽是成为了dp[i][j]，⽽在计算后边的dp[j]的时候会⽤到dp[j-w]，⽽此时的dp[j-w]，已经不再是原来的i-1时刻的状态了，所以在计算是会产⽣⼀定的错误，为了解决这⼀问题可以将j来倒序进⾏计算。优化后的代码：public int knapsack(int W, int N, int[] weights, int[] values) { int[] dp = new int[W + 1]; for (int i = 1; i <= N; i++) { int w = weights[i - 1], v = values[i - 1]; for (int j = W; j >= 1; j--) { if (j >= w) { dp[j] = (dp[j], dp[j - w] + v); } } }

return dp[W];}完全背包第⼆类是完全背包，完全背包是指在01背包的基础上，物品的个数可以使⽤任意个没有限制。解决这类问题只要将01背包内循环的代码改成正序就可以了。多重背包第三类是多重背包，多重背包是指在01背包的基础上，物品的个数有限制可以是0-n个。解决这类问题的思路是将其转化成01背包，具体的⽅法就是n个添加同样属性的物品就可以了。常见问题常见的问题有求最优解，求⽅案数，求能不能达成条件等，以下通过具体问题来介绍问题⼀：分割等和⼦集（LeetCode 416）题⽬描述：给定⼀个只包含正整数的⾮空数组。是否可以将这个数组分割成两个⼦集，使得两个⼦集的元素和相等。注意:每个数组中的元素不会超过 100数组的⼤⼩不会超过 200⽰例 1:输⼊: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11].⽰例 2:输⼊: [1, 2, 3, 5]输出: false解释: 数组不能分割成两个元素和相等的⼦集.解题思路：相当于在数组中取出任意数组合使其和等于数组总和的⼀半实现代码class Solution { public boolean canPartition(int[] nums) { int n = ; int sum = 0; for(int i=0;i=nums[i-1]) dp[i][j] = dp[i-1][j]||dp[i-1][j-nums[i-1]]; else dp[i][j] = dp[i-1][j]; } } return dp[][sum/2]; } //空间优化后的代码 public boolean canPartition2(int[] nums) { int n = ; int sum = 0; for(int i=0;i=nums[i-1];j--){ dp[j] = dp[j]||dp[j-nums[i-1]]; } } return dp[sum/2]; }}问题⼆：⽬标和（LeetCode 494）题⽬描述：给定⼀个⾮负整数数组，a1, a2, …, an, 和⼀个⽬标数，S。现在你有两个符号 + 和 -。对于数组中的任意⼀个整数，你都可以从 + 或 -中选择⼀个符号添加在前⾯。返回可以使最终数组和为⽬标数 S 的所有添加符号的⽅法数。⽰例 1:输⼊: nums: [1, 1, 1, 1, 1], S: 3输出: 5解释:-1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3⼀共有5种⽅法让最终⽬标和为3。注意:数组的长度不会超过20，并且数组中的值全为正数。初始的数组的和不会超过1000。保证返回的最终结果为32位整数。解题思路相当于在数组中找出⼀部分数，使其和为(sum+S)/2实现代码class Solution { public int findTargetSumWays(int[] nums, int S) { int n = ; int sum = 0; for(int i = 0 ;i

if(j>=we) dp[i][j]=dp[i-1][j]+dp[i-1][j-we];

else

dp[i][j]=dp[i-1][j];

} } return dp[n][W]; } //空间优化后dp

public int findTargetSumWays2(int[] nums, int S) { int n = ; int sum = 0; for(int i = 0 ;i =we;j--){ dp[j]=dp[j]+dp[j-we]; }

} return dp[W]; }

}问题三：1和 0（LeetCode 474）题⽬描述：在计算机界中，我们总是追求⽤有限的资源获取最⼤的收益。现在，假设你分别⽀配着 m 个 0 和 n 个 1。另外，还有⼀个仅包含 0 和 1 字符串的数组。你的任务是使⽤给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最⼤数量。每个 0 和 1 ⾄多被使⽤⼀次。注意:给定 0 和 1 的数量都不会超过 100。给定字符串数组的长度不会超过 600。⽰例 1:输⼊: Array = {“10”, “0001”, “111001”, “1”, “0”}, m = 5, n = 3输出: 4解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 “10”,“0001”,“1”,“0” 。⽰例 2:输⼊: Array = {“10”, “0”, “1”}, m = 1, n = 1输出: 2解释: 你可以拼出 “10”，但之后就没有剩余数字了。更好的选择是拼出 “0” 和 “1” 。解题思路⼆维dp，多加⼀层循环就可以实现代码class Solution { public int findMaxForm(String[] strs, int m, int n) { if(strs==null||==0) return 0; int [][]dp=new int[m+1][n+1]; for(int i=0;i<;i++){ int ones=0,zeros=0; for(int j=0;j=zeros;j--){ for(int k=n;k>=ones;k--){ dp[j][k]=(dp[j][k],dp[j-zeros][k-ones]+1); } } } return dp[m][n]; }}问题四：零钱兑换（LeetCode 322）题⽬描述：给定不同⾯额的硬币 coins 和⼀个总⾦额 amount。编写⼀个函数来计算可以凑成总⾦额所需的最少的硬币个数。如果没有任何⼀种硬币组合能组成总⾦额，返回 -1。⽰例 1:输⼊: coins = [1, 2, 5], amount = 11输出: 3解释: 11 = 5 + 5 + 1⽰例 2:输⼊: coins = [2], amount = 3输出: -1说明:你可以认为每种硬币的数量是⽆限的。解题思路完全背包，求最优⽅案值实现代码class Solution { public int coinChange(int[] coins, int amount) { if(==0||amount==0) return 0; int n = ; int [] dp = new int [amount+1]; for(int i=1;i<=n;i++){ int w= coins[i-1]; for(int j=w;j<=amount;j++){ if(j==w)//放⼊第⼀个 dp[j]=1; else if(dp[j]==0&&dp[j-w]!=0) dp[j]=dp[j-w]+1; else if(dp[j-w]!=0) dp[j]=(dp[j],dp[j-w]+1); } } return dp[amount]==0?-1:dp[amount]; }}问题五：零钱兑换II（LeetCode518）题⽬描述给定不同⾯额的硬币和⼀个总⾦额。写出函数来计算可以凑成总⾦额的硬币组合数。假设每⼀种⾯额的硬币有⽆限个。⽰例 1:输⼊: amount = 5, coins = [1, 2, 5]输出: 4解释: 有四种⽅式可以凑成总⾦额:5=55=2+2+15=2+1+1+15=1+1+1+1+1⽰例 2:输⼊: amount = 3, coins = [2]输出: 0解释: 只⽤⾯额2的硬币不能凑成总⾦额3。⽰例 3:输⼊: amount = 10, coins = [10]输出: 1注意:你可以假设：0 <= amount (总⾦额) <= 50001 <= coin (硬币⾯额) <= 5000硬币种类不超过 500 种结果符合 32 位符号整数解题思路完全背包求⽅案数问题实现代码class Solution { public int change(int amount, int[] coins) { if(amount==0) return 1; if(coins==null||==0) return 0; int n = ; int [] dp = new int [amount+1]; dp[0]=1; for(int i=1;i<=n;i++){ int w = coins[i-1]; for(int j=w;j<=amount;j++){ dp[j]=dp[j]+dp[j-w]; } } return dp[amount]; }}问题六：单词拆分（LeetCode139）题⽬描述给定⼀个⾮空字符串 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解题思路完全背包问题，有顺序要求，遍历的循环放在⾥边实现代码class Solution { public boolean wordBreak(String s, List wordDict) { int n = (); boolean [] dp = new boolean [n+1]; dp[0]=true; for(int i=1;i<=n;i++){ for(String word:wordDict){//求解顺序完全背包问题对物品的迭代应该放在⾥层 int w = (); if(i>=w&&(ing(i-w,i))){ dp[i]=dp[i]||dp[i-w]; } } } return dp[n]; }}问题七：组合总数IV（LeetCode377）题⽬描述给定⼀个由正整数组成且不存在重复数字的数组，找出和为给定⽬标正整数的组合的个数。⽰例:nums = [1, 2, 3]target = 4所有可能的组合为：(1, 1, 1, 1)(1, 1, 2)(1, 2, 1)(1, 3)(2, 1, 1)(2, 2)(3, 1)请注意，顺序不同的序列被视作不同的组合。因此输出为 7。解题思路完全背包求⽅案数问题实现代码class Solution { public int combinationSum4(int[] nums, int target) { int n = ; int []dp = new int [target+1]; dp[0]=1; for(int i=1;i<=target;i++){ for( int j=1;j<=n;j++){ int w = nums[j-1]; if(i>=w) dp[i]=dp[i]+dp[i-w]; } } return dp[target]; }}