【Leetcode】最小 subsetsum

给定一个数组和一个target，找出最少的元素和为target。

其实是一个subsetsum问题，之前的subsetsum存储的是boolean，这里存长度即可。

定义子问题dp[i][j]为使用前j个元素达到和i的最小长度，那么dp[i][j]首先可以使用dp[i][j - 1]的结果。然后再看能否使用array[j]，那么就要看dp[i-array[j]][j-1]的值了。

代码：

public int minSetSum(int[] array, int target){ int[][] dp = new int[target + 1][array.length]; for(int i = 1; i <= target; i++){ for(int j = 0; j < array.length; j++){ if(j >= 1 && dp[i][j - 1] > 0) dp[i][j] = dp[i][j - 1]; if(i - array[j] >= 0 && j >= 1){ if(i == array[j]) dp[i][j] = 1; else if(dp[i - array[j]][j - 1] > 0) dp[i][j] = dp[i][j] == 0?dp[i - array[j]][j - 1] + 1:Math.min(dp[i][j], dp[i - array[j]][j - 1] + 1); } } } return dp[target][array.length - 1]; }复杂度为length*target dp问题的两个特征

（1）子问题；

（2）重叠。

可以解决的问题有 最优解问题，数目问题等。通常来讲返回所有解的问题无法用dp，当然不是绝对。