郑州400建站网站建设,广东省建设监理协会网站官网,咸宁抖音seo收费标准,做简单的html网站本题中#xff0c;是要求nums中求的总和为target的排列数#xff0c;因为题中说了#xff0c;元素顺序不同#xff0c;则可以视为不同的结果之一。
所以#xff0c;根据对背包问题的总结#xff0c;本题中元素可以重复使用#xff0c;是完全背包并且需要求排列数#… 本题中是要求nums中求的总和为target的排列数因为题中说了元素顺序不同则可以视为不同的结果之一。
所以根据对背包问题的总结本题中元素可以重复使用是完全背包并且需要求排列数则我们需要考虑遍历顺序先遍历背包(target)再遍历物品nums。并且在遍历背包的时候我们应该采用正序遍历因为是可以重复使用元素的。
递推公式dp[j] dp[j-nums[i]]。并且我们在初始化的时候dp[0]应该为1否则得出的结果就都是0了。
注意这里背包也从0开始遍历但是在最后写递推公式的时候需要满足inums[j]这样才能保证dp[i-nums[j]]索引正常。
class Solution {public int combinationSum4(int[] nums, int target) {int n nums.length;int[] dp new int[target1];dp[0] 1;for(int i 0;itarget;i){for(int j 0;jn;j){if(inums[j]){dp[i] dp[i-nums[j]];}}}return dp[target];}
}
