Time Complexity of dynamic programming vs recursion?


  • 0
    A

    As the title says, what should be the time complexity of using dynamic programming vs recursion? At first glance, I think dp is polynomial time while recursion may use up to exponential time, however, I implemented in both ways and found out dp solution takes more time.

    The following are my recursive and dp solutions:

    dp:

      public class Solution {
            class Result {
                List<List<Integer>> res;
                
                Result() {
                    res = new ArrayList<List<Integer>>();
                }
                
                void add(List<Integer> comb) {
                    res.add(comb);
                }
            }
            
            public List<List<Integer>> combinationSum2(int[] num, int target) {
                Arrays.sort(num);
                Result[][] DP = new Result[target+1][num.length+1];
                for (int i=0; i<=target; i++) {
                    DP[i][num.length] = new Result();
                }
                DP[0][num.length].add(new LinkedList<Integer>());
                for (int j=num.length-1; j>=0; j--) {
                    int candi = num[j];
                    for (int i=0; i<=target; i++) {
                        DP[i][j] = new Result();
                        if (i>0 && i < candi) continue;
                        for (int k=0; k<= (i >= candi ? 1 : 0); k++) {
                            int t = j+1;
                            if (k==0) {
                                while (t < num.length && num[t] == candi) t++;
                            }
                            for (List<Integer> comb : DP[i-k*candi][t].res) {
                                LinkedList<Integer> newComb = new LinkedList(comb);
                                if (k > 0)
                                    newComb.add(0, candi);
                                DP[i][j].add(newComb);
                            }
                        }
                    }
                }
                return DP[target][0].res;
            }
        }
    

    recursive:

    public List<List<Integer>> combinationSum2(int[] num, int target) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            List<Integer> current = new ArrayList<Integer>();
            Arrays.sort(num);
            combinationSum2(result, current, num, 0, target);
            return result;
        }
        
        private void combinationSum2(List<List<Integer>> result, List<Integer> current, 
            int[] num, int startIdx, int target) {
            if (target == 0) {
                result.add(new ArrayList<Integer>(current));
                return;
            } 
            
            if (startIdx >= num.length || num[startIdx] > target) {
                return;
            }
            
            if (target >= num[startIdx]) {
                current.add(num[startIdx]);
                combinationSum2(result, current, num, startIdx+1, target - num[startIdx]);
                current.remove(current.size()-1);
            }
            while (startIdx < num.length - 1 && num[startIdx] == num[startIdx+1])
                startIdx++;
            combinationSum2(result, current, num, startIdx+1, target);
        }

  • 0
    X

    I have the same question.


Log in to reply
 

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