二维棋盘问题的区间动态规划通用解法：当数据量较小时，可以考虑使用动态规划。dp[row1][col1][row2][col2] 代表从位置 (row1, col1) 到 (row2, col2) 的子矩形所需的代价。状态转移可通过横向切割或纵向切割来完成。该算法的时间复杂度为 O(m2⋅n2⋅(m+n))。

其中，row和col可以换成width和height，而对二维范围内的具体事务可以用二维前缀和或容斥原理表示。

力扣1444. 切披萨的方案数

典型的二维数组统计+区间dp分割。
因为不需要对切过的披萨再操作，所以dp[x][y]直接表示(x,y)到(m-1,n-1)的所有切法。

#define MOD 1000000007
#define query(i, j) (s[m][n] - s[i][n] - s[m][j] + s[i][j])
class Solution {
public:
    int ways(vector<string>& pizza, int k) {
        int m = pizza.size(), n = pizza[0].size();
        vector<vector<vector<int>>> f(
            m, vector<vector<int>>(n, vector<int>(k, -1)));
        vector<vector<int>> s(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                int x = pizza[i - 1][j - 1] == 'A' ? 1 : 0;
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
            }
        }

        vector<vector<vector<int>>> dp(
            k + 1, vector<vector<int>>(m, vector<int>(n, 0))); // dp[k][m][n]
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (query(i, j) > 0)
                    dp[0][i][j] = 1;
                else
                    dp[0][i][j] = 0;
        for (int kk = 1; kk <= k; kk++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (query(i, j) == 0)
                        continue;
                    for (int i2 = i + 1; i2 < m; i2++) {
                        if (query(i, j) - query(i2, j) > 0) {
                            dp[kk][i][j] =
                                (dp[kk][i][j] + dp[kk - 1][i2][j]) % MOD;
                        }
                    }
                    for (int j2 = j + 1; j2 < n; j2++) {
                        if (query(i, j) - query(i, j2) > 0) {
                            dp[kk][i][j] =
                                (dp[kk][i][j] + dp[kk - 1][i][j2]) % MOD;
                        }
                    }
                }
            }
        }
        return dp[k - 1][0][0];
    }
};

力扣2312. 卖木头块

因为不受位置限制所以只讨论长宽即可

class Solution {
public:
    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
        vector<vector<int>>pay(m+1,vector<int>(n+1,0));
        vector<vector<long long int>>dp(m+1,vector<long long int>(n+1,0));
        for(auto price:prices)pay[price[0]][price[1]]=price[2],dp[price[0]][price[1]]=price[2];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                long long int &x=dp[i][j];
                for(int k=1;k<i;k++){
                    x=max(x,dp[k][j]+dp[i-k][j]);
                }
                for(int k=1;k<j;k++){
                    x=max(x,dp[i][k]+dp[i][j-k]);
                }
            }
        }
        return dp[m][n];
    }
};

AtCoder - abc233_g Strongest Takahashi

方阵是个小干扰项，仍然按区间dp遍历即可。
关于内层遍历一开始最大取max(h,w)是否会导致结果偏大：不会，包含他的块会随着k的遍历在外层整体上取较小的值，因此只要最后整体矩阵是方阵就无事。

#include<bits/stdc++.h>
using namespace std;
int N;
string mp[55];
int dp[55][55][55][55]={0};
int main() {
    memset(dp,0x3f3f3f3f,sizeof dp);
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>mp[i];
        mp[i]="?"+mp[i];
    }
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(mp[i][j]=='#')dp[i][j][i][j]=1;
            else dp[i][j][i][j]=0;
        }
    }
    for(int h=1;h<=N;h++){
        for(int w=1;w<=N;w++){
            for(int a=1;a<=N;a++){
                for(int b=1;b<=N;b++){
                    int c=a+h-1;
                    int d=b+w-1;
                    if(c>N||d>N)continue;
                    int &x=dp[a][b][c][d];
                    if(x==0x3f3f3f3f)x=max(w,h);
                    for(int k=a;k<c;k++){
                        x=min(x,dp[a][b][k][d]+dp[k+1][b][c][d]);
                    }
                    for(int k=b;k<d;k++){
                        x=min(x,dp[a][b][c][k]+dp[a][k+1][c][d]);
                    }
                }
            }
        }
    }


    cout<<dp[1][1][N][N]<<endl;
    return 0;
}

力扣3218. 切蛋糕的最小总开销 I

这个题也可以用贪心或克鲁斯卡尔做，在这仅作示范

class Solution {
public:
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut) {
        vector<vector<vector<vector<int>>>> dp(m,vector<vector<vector<int>>>(n,vector<std::vector<int>>(m,vector<int>(n, 0x3f3f3f3f))));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                dp[i][j][i][j]=0;
            }
        }
        for(int w=1;w<=n;w++){
            for(int h=1;h<=m;h++){
                for(int i1=0;i1<m;i1++){
                    for(int j1=0;j1<n;j1++){
                        int i2=i1+h-1;
                        int j2=j1+w-1;
                        if(i2>=m||j2>=n)continue;
                        int &x=dp[i1][j1][i2][j2];
                        for(int k=i1;k<i2;k++){
                            x=min(x,dp[i1][j1][k][j2]+dp[k+1][j1][i2][j2]+horizontalCut[k]);
                        }
                        for(int k=j1;k<j2;k++){
                            x=min(x,dp[i1][j1][i2][k]+dp[i1][k+1][i2][j2]+verticalCut[k]);
                        }
                    }
                }
            }
        }
        return dp[0][0][m-1][n-1];
    }
};