The difference of two java DP solution of Combination Sum IV


  • 0
    C

    solution 1 : (correct one)

    public class Solution {
    
        public int combinationSum4(int[] nums, int target) {
            // 在递归过程中,如果状态集是有限的,我们可以采用动态规划的方法,把每个状态的结果记录下来,以减少计算量。
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for (int i = 1; i < dp.length; i++) {        //  outer loop is  to  traversal  dp array 
                for (int j = 0; j < nums.length; j++) {    // inner loop is to  traversal  nums array  
                    if (i - nums[j] >= 0) {
                        dp[i] += dp[i - nums[j]];
                    }
                }
            }
            return dp[target];
        }
        
    }
    

    solution 2:(wrong one )

    public class Solution {
        
        public int combinationSum4(int[] nums, int target) {
            int [] dp = new int[target + 1];
            
            dp[0] = 1;
            for (int i = 0; i < nums.length; i++) {        //  outer loop is  to  traversal  nums array and nums array should be ASC ordered
                for (int j = nums[i]; j <= target; j++) {   //  inner loop is to  traversal  dp array  
                    dp[j] += dp[j - nums[i]];
                }
            }
            return dp[target];
        }
        
    }
    

    when give a testcase:

    nums = [1, 2, 3]
    target = 4

    solution 1 got the answer 7:
    The possible combination ways are:
    (1, 1, 1, 1)
    (1, 1, 2)
    (1, 2, 1)
    (1, 3)
    (2, 1, 1)
    (2, 2)
    (3, 1)
    i wanna say this is Permutations not combination.

    solution 2 give the answer 4, Obviously, delete the same combination from the above possible Permutations, eg (1, 1, 2) (1, 2, 1) (2, 1, 1) (1, 3) (3, 1), the answer is 4.

    so, solution 1 could get the Permutation Sum, and solution 2 could get the Combination Sum. this is because the count order of dp and nums is different.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.