# 2184. Number of Ways to Build Sturdy Brick Wall
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Bit Manipulation`
Link: https://leetcode.com/problems/number-of-ways-to-build-sturdy-brick-wall/
## 思路
首先generate出来每一层所有有可能的mask(mask当中记录每个brick的结束位置)
然后再用dp计算出答案
## Code

class Solution {
    public int buildWall(int height, int width, int[] bricks) {
        List<Integer> masks = new ArrayList<>();
        getAllMasks(width, bricks, 0, 0, masks);
        int[][] dp = new int[height][1024];
        for(int mask:masks) dp[0][mask]=1;
        for(int i=1; i<height; i++){
            for(int mask:masks){
                for(int prevMask:masks){
                    if((mask&prevMask)==0) dp[i][mask] = (dp[i-1][prevMask]+dp[i][mask])%1000000007;
                }
            }
        }
        int ans = 0;
        for(int mask:masks){
            ans = (ans+dp[height-1][mask])%1000000007;
        }
        return ans;
    }
    private void getAllMasks(int width, int[] bricks, int mask, int currWidth, List<Integer> masks){
        if(currWidth==width){
            masks.add(mask);
        }
        else{
            for(int brick:bricks){
                if(currWidth+brick>width) continue;
                if(currWidth+brick<width) mask += 1<<(currWidth+brick);
                getAllMasks(width, bricks, mask, currWidth+brick, masks);
                if(currWidth+brick<width) mask -= 1<<(currWidth+brick);
            }
        }
    }
}