My 0ms C++ DP solution


  • 4
    5
    class Solution {
    public:
        int combinationSum4(vector<int>& nums, int target) {
            int n = nums.size();
            int f[target + 1] = {0};
            f[0] = 1;
            for (int i = 0; i <= target; ++i) {
                if (f[i] == 0) {
                    continue;
                }
                for (int j = 0; j < n; ++j) {
                    int t = i + nums[j];
                    if (t <= target) {
                        f[t] += f[i];
                    }
                }
            }
            return f[target];
        }
    };
    

  • 0
    Z

    Wow, your solution is better than My 3ms Java DP solution.
    Your complexity is O(n*target) but that solution's complexity is O(max{Array.sort(), n*target}).
    So as the fastest java sort algorithm, the complexity is O(n*logn) and as a result, your solution is faster than that solution when logn > target.

    Thumb up~


Log in to reply
 

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