Dynamic programming solution and why DP is slow for this problem


  • 1
    D

    I have been wondering why top solutions are recursion instead of Dynamic Programming although DP is canonical solution for this kind of problems.

    DP is much slower for this problem because this problem requires to get the list of combinations. Therefore, DP uses a lot of memory and time, especially when using vector as insertion in vector is slow. (Anyone has an idea to fix this?)

    When only counting the number of combinations, DP is much faster with O(target * candidates.size()) time (I am not sure about complexity of recursion, anyone has suggestion?).

    The solutions is based on the division: number of combinations to target t using candidate set S = number of combination to target t with at least one of s0 using candidate set S + number of combination to target t without s0 using candidate set S excluding s0. (DP and Backtrack2 solutions in the following uses this)
    f(t | S) = f(t - s0 | S) + f(t | S - s0)

    This can be expanded further so we can use a loop in the recursion function (Backtrack1 solution in the following uses this)
    f(t | S) = f(t - s0 | S) + f(t - s0 - s1 | S - s0) + ... + f(t - s0 - s1 -...- sn | S - s0 -... - s(n-1))

    I tested 2 cases:

    1. Get the list of combinations: DP is slower
    2. Only count the number of combinations: DP is very much faster.

    Case 1 code:

    
    using namespace chrono;
    
    class SolutionDP {
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
          if (candidates.empty())
            return vector<vector<int>>();
          sort(candidates.begin(), candidates.end());
    
            vector<int> combs(target + 1);
            vector<vector<vector<int>>> result(target+1);
    
    
            for (int j = 0; j <= target; ++j) {
                result[j].reserve(target/candidates[0]);
              if (j % candidates[0] ==0) {
                    combs[j] = 1;
                    result[j] = vector<vector<int>>(1, vector<int>(j / candidates[0], candidates[0]));
              }
           }
    
            for (int i = 1; i < candidates.size(); ++i) {
            for (int j = candidates[i]; j <= target; ++j) {
              combs[j] += combs[j - candidates[i]];
              for (vector<int> tmp : result[j - candidates[i]]) {
                tmp.emplace_back(candidates[i]);
                result[j].emplace_back(tmp);
              }
            }
            }
    
          return result.back();
        }
    };
    
    
    class SolutionBacktrack1 {
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            vector<vector<int>> result;
            vector<int> comb;
            combinationSumRecursive(result, candidates, target, 0, comb);
            return result;
        }
    
        void combinationSumRecursive(vector<vector<int>>& result, const vector<int>& candidates, int target, int canidx, vector<int>& comb) {
            if (target < 0)
                return;
            if (target == 0) {
                result.emplace_back(comb);
                return;
            }
            for (int i = canidx; i < candidates.size(); ++i) {
                comb.emplace_back(candidates[i]);
                combinationSumRecursive(result, candidates, target - candidates[i], i, comb);
                comb.pop_back();
            }
        }
    };
    
    class SolutionBacktrack2 {
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            vector<vector<int>> result;
            vector<int> comb;
            combinationSumRecursive(result, candidates, target, 0, comb);
            return result;
        }
    
        void combinationSumRecursive(vector<vector<int>>& result, const vector<int>& candidates, int target, int canidx, vector<int>& comb) {
            if (target == 0) {
                result.emplace_back(comb);
                return;
            }
            if (canidx < candidates.size() - 1)
                combinationSumRecursive(result, candidates, target, canidx + 1, comb);
            if (candidates[canidx] <= target) {
                comb.emplace_back(candidates[canidx]);
                combinationSumRecursive(result, candidates, target - candidates[canidx], canidx, comb);
                comb.pop_back();
            }
        }
    };
    
    int main() {
      SolutionDP sol_dp;
      SolutionBacktrack1 sol_bt1;
      SolutionBacktrack2 sol_bt2;
      vector<int> cand{2,3,6,7};
      int target = 140;
    
      high_resolution_clock::time_point t1 = high_resolution_clock::now();
      cout << sol_dp.combinationSum(cand, target).size() << endl;
      high_resolution_clock::time_point t2 = high_resolution_clock::now();
      cout << duration_cast<microseconds>( t2 - t1 ).count() << endl; // 18189 usec
    
      t1 = high_resolution_clock::now();
      cout << sol_bt1.combinationSum(cand, target).size() << endl;
      t2 = high_resolution_clock::now();
      cout << duration_cast<microseconds>( t2 - t1 ).count() << endl; // 691 usec
    
      t1 = high_resolution_clock::now();
      cout << sol_bt2.combinationSum(cand, target).size() << endl;
      t2 = high_resolution_clock::now();
      cout << duration_cast<microseconds>( t2 - t1 ).count() << endl; // 607 usec
    
      return 0;
    }
    

    Case 2 code:

    #include <chrono>
    
    using namespace chrono;
    
    class SolutionDP {
    public:
      int combinationSum(vector<int>& candidates, int target) {
        if (candidates.size() == 0)
          return 0;
        vector<int> combs(target + 1);
        for (int j = 0; j <= target;++j) {
          if (j % candidates[0] == 0)
            combs[j] = 1;
        }
    
        for (int i = 1; i < candidates.size(); ++i) {
          for (int j = candidates[i]; j <= target; ++j) {
            combs[j] += combs[j - candidates[i]];
          }
        }
        return combs.back();
      }
    
    };
    
    
    class SolutionBacktrack1 {
    public:
      int combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        int num_combs = 0;
        combinationSum(num_combs, candidates, target, 0);
        return num_combs;
      }
    
      void combinationSum(int& num_combs, const vector<int>& candidates, int target, int begin) {
        if (target == 0) {
          num_combs++;
          return;
        }
    
        for (int i = begin; i < candidates.size() && target >= candidates[i]; ++i) {
          combinationSum(num_combs, candidates, target - candidates[i], i);
        }
      }
    };
    
    class SolutionBacktrack2 {
    public:
      int combinationSum(vector<int>& candidates, int target) {
        int num_combs = 0;
        combinationSum(num_combs, candidates, target, 0);
        return num_combs;
      }
      void combinationSum(int& num_combs, const vector<int>& candidates, int target, int begin) {
        if (!target) {
          ++num_combs;
          return;
        }
    
        if (begin < candidates.size() - 1)
          combinationSum(num_combs, candidates, target, begin + 1);
        if (target >= candidates[begin])
          combinationSum(num_combs, candidates, target - candidates[begin], begin);
      }
    };
    
    int main() {
      SolutionDP sol_dp;
      SolutionBacktrack1 sol_bt1;
      SolutionBacktrack2 sol_bt2;
      vector<int> cand{2,3,6,7};
      int target = 1400;
    
      high_resolution_clock::time_point t1 = high_resolution_clock::now();
      cout << sol_dp.combinationSum(cand, target) << endl;
      high_resolution_clock::time_point t2 = high_resolution_clock::now();
      cout << duration_cast<microseconds>( t2 - t1 ).count() << endl; // 30 usec
    
      t1 = high_resolution_clock::now();
      cout << sol_bt1.combinationSum(cand, target) << endl;
      t2 = high_resolution_clock::now();
      cout << duration_cast<microseconds>( t2 - t1 ).count() << endl; // 1777237 usec
    
      t1 = high_resolution_clock::now();
      cout << sol_bt2.combinationSum(cand, target) << endl;
      t2 = high_resolution_clock::now();
      cout << duration_cast<microseconds>( t2 - t1 ).count() << endl; // 1384665 usec
    
      return 0;
    }
    

  • 1
    K

    You don't have to use vectors in your DP table. Store true/false depending on whether a solution can be made from the given state (row/col in DP table). After you build the table, generate the answers using the standard DFS approach, but only explore paths that lead to answers (i.e., no backtracking).

    Example: http://pastebin.com/9p6M7DVr


Log in to reply
 

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