# 1240. Tiling a Rectangle with the Fewest Squares
###### tags: `Leetcode` `Hard` `Dynamic Programming` `Backtracking`
Link: https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/description/
## 思路
把一开始的解法放在最后面了 那种解法只对要吗就横着切要吗就竖着切的有效
这个case就无效了
思路[参考](https://leetcode.com/problems/tiling-a-rectangle-with-the-fewest-squares/solutions/417654/6ms-clean-java-backtrack-solution-with-detailed-explanation/)
backtracking填满board
每次找到leftmost topmost还没被填满的点 然后试着放所有possible size的square 再接着往下backtracking
## Code

class Solution {
    int ans, m, n;
    public int tilingRectangle(int m, int n) {
        this.m = m;
        this.n = n;
        ans = n*m;
        int[][] board = new int[m][n];
        backtracking(board, 0);
        return ans;
    }
    private void backtracking(int[][] board, int curr){
        if(curr > ans) return;
        int x = -1, y = -1;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(board[i][j]==0){
                    x=i;
                    y=j;
                    break;
                }
            }
            if(x!=-1 && y!=-1) break;
        }
        if(x==-1 && y==-1) ans = Math.min(ans, curr);
        else{
            int len = findLen(x, y, board);
            for(int i=1; i<=len; i++){
                cover(x, y, i, board, 1);
                backtracking(board, curr+1);
                cover(x, y, i, board, 0);
            }
        }
    }
    private int findLen(int x, int y, int[][] board){
        int len = 1;
        while(x+len<m && y+len<n){
            boolean flag = false;
            for(int i=0; i<=len; i++){
                if(board[x+len][y+i]==1 || board[x+i][y+len]==1){
                    flag = true;
                    break;
                }
            }
            if(flag) break;
            len++;
        }
        return len;
    }
    private void cover(int x, int y, int len, int[][] board, int num){
        for(int i=x; i<x+len; i++){
            for(int j=y; j<y+len; j++){
                board[i][j] = num;
            }
        }
    }
}

一开始的解法

class Solution {
    public int tilingRectangle(int n, int m) {
        int[][] dp = new int[n+1][m+1];
        return dfs(n, m, dp);
    }
    private int dfs(int n, int m, int[][] dp){
        if(dp[n][m]!=0) return dp[n][m];
        if(n==m) return dp[m][n] = 1;
        int ans = Integer.MAX_VALUE;
        for(int i=1; i<=Math.min(m,n); i++){
            if(n>m) ans = Math.min(ans, dfs(n-i, m, dp)+dfs(i, m, dp));
            else ans = Math.min(ans, dfs(n, m-i, dp)+dfs(n, i, dp));
        }
        return dp[n][m] = ans;
    }
}