Java DP, Same as fibonacci

  • 0
    public int combinationSum4(int[] nums, int target) {
            if(nums == null) return 0;
            int[] dp = new int[target+1];
               for(int i =0;i<=target;i++) 
                for(int n:nums)
                        dp[i] +=dp[i-n];
            return dp[target];

    I was thinking it's complete knapsack problem. But actually it's not.
    Since [1,1,2] and [1,2,1] is considered as different way here.
    So we can think this is extended Fibonacci problem, where dp[i] += dp[k] where k is from 0, i-1.

Log in to reply

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