Solution

Method 1 – DP with Bitmask (Backtracking)

Intuition

For each subset of points, we can cover them with a single line if they are collinear. Use DP with bitmask: for each mask, try all possible lines, and recursively cover the rest. The answer is the minimum number of lines needed to cover all points.

Approach

For each pair of points, find all points collinear with them.
Use DP: dp[mask] = min number of lines to cover points in mask.
For each mask, try all possible lines, update dp.
Return dp[full_mask].

Code

[{"language":"C++","code":"#include <vector>\nusing namespace std;\nclass Solution {\npublic:\n    int minLines(vector<vector<int>>& points) {\n        int n = points.size();\n        vector<vector<int>> col(n, vector<int>(n, 0));\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j < n; ++j) {\n                int mask = 0;\n                for (int k = 0; k < n; ++k) {\n                    int x1 = points[i][0], y1 = points[i][1];\n                    int x2 = points[j][0], y2 = points[j][1];\n                    int x3 = points[k][0], y3 = points[k][1];\n                    if ((x2-x1)*(y3-y1) == (y2-y1)*(x3-x1)) mask |= 1<<k;\n                }\n                col[i][j] = mask;\n            }\n        }\n        vector<int> dp(1<<n, n);\n        dp[0] = 0;\n        for (int mask = 0; mask < (1<<n); ++mask) {\n            if (dp[mask] == n) continue;\n            int first = 0;\n            while (first < n && !(mask & (1<<first))) ++first;\n            if (first == n) continue;\n            for (int j = 0; j < n; ++j) {\n                int new_mask = mask | col[first][j];\n                dp[new_mask] = min(dp[new_mask], dp[mask] + 1);\n            }\n        }\n        return dp[(1<<n)-1];\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabind

Related Tags