LeetCode

Editorial: LeetCode 1621 Number of Sets of K Non Overlapping Line Segments

Editorial: LeetCode 1621 Number of Sets of K Non Overlapping Line Segments

https://leetcode.com/problems/number-of-sets-of-k-non-overlapping-line-segments/ from Amazon

Thinking process: We want to count the number of ways for drawing those line segments. So, if our input is (n, k), once we determinte the first line, like the red line in the example, we can delegate this problem to someone else and ask them to return the number of (n-x, k-1), where x will change based on your choice of the first line.

This is the pattern of recursion!! We decide what will it look like for part of the solution, and then we delegate the sub-problem to someone else (Notice that the problem size decreases after our choice).

So, I came out something below. Line 13 to 16 was my first version, which was a naive observation from the examples. However, this was too slow since we do O(n) work in every sub-problem. If we look into the formula from line 13 to 16 carefully, we can derive the new fomula in line 18, which is constant amount of work and improves the time complexity a lot. Finally, we need a dp array to cache the answer (standard memorization recursion).

 1typedef long long ll;
 2class Solution {
 3public:
 4    int MOD = 1e9 + 7;
 5    vector<vector<int>> dp;
 6    int dfs(int n, int k) {
 7        if (n == k) return 1;
 8        if (n < k) return 0;
 9        if (dp[n][k]) return dp[n][k];
10        if (k == 1) return dp[n][k] = ((n+1)*n/2)%MOD;
11        ll ret = 0;
12        // if (n <= k+2) {
13        //     for (int i=1; i<=n-k+1; i++) {
14        //         ret += (ll)i*dfs(n-i, k-1);
15        //         ret %= MOD;
16        //     }
17        // } else {
18            ret += ((ll)2*dfs(n-1, k) + dfs(n-1, k-1) - dfs(n-2, k));
19            ret %= MOD;
20            if (ret < 0) ret += MOD;
21        // }
22        return dp[n][k] = ret;
23    }
24    int numberOfSets(int n, int k) {
25        dp.resize(n, vector<int>(k+1));
26        return dfs(n-1, k);
27    }
28};
comments powered by Disqus