Java DP, Same as fibonacci


  • 0
    C
    public int combinationSum4(int[] nums, int target) {
            if(nums == null) return 0;
            int[] dp = new int[target+1];
            dp[0]=1;
               for(int i =0;i<=target;i++) 
                for(int n:nums)
                    if(i>=n)
                        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.