首页 > 代码库 > 377. Combination Sum IV
377. Combination Sum IV
是看到discuss里面的解法，因为用backtracking实在太多可能性了
思路是和https://leetcode.com/problems/climbing-stairs/
在climbing stairs里面假如有n个台阶，每次可以跨一个台阶或者两个台阶，那么它的状态转移方程是res[i] = res[i - 1] + res[i - 2]，初始化是res[0] = 1; res[1] = 1;
但是在本题中，每次不再只是可以跨一步或者两步了，每次可以跨nums数组里面的任意数字的步，而且终点不是n了，终点是target数。所以状态转移方程是
foreach possible number in nums: res[i] += res[i - each] (i - each >= 0)
而且其中等于0也没有关系我们把res[0]初始化成1就好了。
1 public int combinationSum4(int[] nums, int target) { 2 if(nums.length == 0) { 3 return 0; 4 } 5 Arrays.sort(nums); 6 int[] res = new int[target + 1]; 7 res[0] = 1; 8 for(int i = 1; i <= target; i++) { 9 for(int num: nums) {10 if(i - num >= 0) {11 res[i] += res[i - num];12 } else {13 break;14 }15 }16 }17 return res[target];18 }
注意arrays要sort。因为dp是从小往大走的，我们会希望处理到后面的时候前面的结果已经处理好可以用了。
377. Combination Sum IV
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。