Recursive is faster than dp?


  • 2
    G

    // recursion solution

    public class Solution {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(n < 0 || n < k){ return result;}
        if(k == 1){
            for(int i = 1; i <= n; i++){
                List<Integer> temp = new ArrayList<Integer>();
                temp.add(i);
                result.add(temp);
            }
            return result;
        }
        result = combine(n-1, k-1);
        for(int i = 0; i < result.size(); i++){
            result.get(i).add(n);
        }
        List<List<Integer>> temp = combine(n-1, k);
        result.addAll(temp);
        return result;
    }
    

    }

    // dp solution

    public class Solution {

    public List<List<Integer>> combine(int n, int k) {

        List<List<List<List<Integer>>>> dp = new ArrayList<List<List<List<Integer>>>>();
        List<List<List<Integer>>> line = new ArrayList<List<List<Integer>>>();
        List<List<Integer>> cell = new ArrayList<List<Integer>>();
        List<Integer> entry = new ArrayList<Integer>();
        entry.add(1);
        cell.add(entry);
        line.add(cell);
        dp.add(line);
        for(int i = 1; i < k; i++){
            List<List<Integer>> cellI = new ArrayList<List<Integer>>();
            line.add(cellI);
        }
        
        for(int i = 1; i < n; i++){
            List<List<List<Integer>>> newLine = new ArrayList<List<List<Integer>>>();
            newLine.add(new ArrayList<List<Integer>>(dp.get(i-1).get(0)));
            List<Integer> temp = new ArrayList<Integer>();
            temp.add(i+1);
            newLine.get(0).add(temp);
            dp.add(newLine);
        }
        for(int i = 1; i < n; i++){
            for(int j = 1; j < k; j++){
                List<List<Integer>> newCell = new ArrayList<List<Integer>>();
                List<List<Integer>> pre = dp.get(i-1).get(j);
                for(int m = 0; m < pre.size(); m++){
                	newCell.add(new ArrayList<Integer>(pre.get(m)));
                }
                List<List<Integer>> previous = dp.get(i-1).get(j-1);
                for(int m = 0; m < previous.size(); m++){
                    List<Integer> entryTemp = new ArrayList<Integer>(previous.get(m));
                    entryTemp.add(i+1);
                    newCell.add(entryTemp);
                }
    
                dp.get(i).add(newCell);
            }
        }
        return dp.get(n-1).get(k-1);
    }
    

    }


Log in to reply
 

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