# 2152. Minimum Number of Lines to Cover Points
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/minimum-number-of-lines-to-cover-points/
## 思路 $O(2^N)$ $O(2^N)$
参考[【每日一题】LeetCode 2152. Minimum Number of Lines to Cover Points](https://www.youtube.com/watch?v=b3utVAF0ER8&ab_channel=HuifengGuan)
$state$的每一位表示对应的$points$有没有被算进来
$dp[state]$代表当前$state$最少需要用几条直线串起来

列举子集的模版code

for(int substate = state; substate > 0; substate = (substate-1)&state){}

## Code

class Solution {
    public int minimumLines(int[][] points) {
        int n = points.length;
        int[] dp = new int[1<<n];
        Arrays.fill(dp, Integer.MAX_VALUE/2);
        for(int state = 1; state < (1<<n); state++){
            if(formALine(points, state)){
                dp[state] = 1;
            }
        }
        for(int state = 1; state < (1<<n); state++){
            for(int substate = state; substate > 0; substate = (substate-1)&state){
                dp[state] = Math.min(dp[state], dp[substate]+dp[state-substate]);
            }
        }
        return dp[(1<<n)-1];
    }
    public boolean formALine(int[][] points, int state){
        List<Integer> tempPoints = new ArrayList<>();
        for(int i = 0;i < points.length;i++){
            if(((state>>i)&1)==1){
                tempPoints.add(i);
            }
        }
        if(tempPoints.size()<=2){
            return true;
        }
        for(int i = 2;i < tempPoints.size();i++){
            int a = tempPoints.get(0), b = tempPoints.get(1), c = tempPoints.get(i);
            if((points[c][1]-points[b][1])*(points[c][0]-points[a][0])!=(points[c][1]-points[a][1])*(points[c][0]-points[b][0])) return false;
        }
        return true;
    }
}