Leetcode Problem 2152. Minimum Number of Lines to Cover Points

Algorithm

1. Initialize a DP array dp with size 2^n (where n is the number of points) and set all values to a large number (e.g., INT_MAX).
2. For each point, set dp[1 << i] to 1, as each point alone can be covered by a single line.
3. Iterate over all pairs of points (i, j) and calculate the line they form. Use the GCD of the differences in x and y coordinates to normalize the slope.
4. For each pair (i, j), iterate over all other points k to check if they lie on the same line. If so, include them in the bitmask.
5. Update the dp array for the bitmask representing points (i, j, k...) on the same line to 1.
6. Iterate over all possible bitmasks and update the dp array using the formula dp[i] = min(dp[i], dp[j] + dp[i - j]) for all j that are subsets of i.
7. Return dp[(1 << n) - 1] as the answer, which represents the minimum number of lines needed to cover all points.