棋盤分割

作者 | 小 K

出品 | 公衆號：小 K 算法 （ID：xiaok365）

01 故事起源

有一個 8*8 的棋盤，沿着格子的邊進行分割，每分割一塊拿走，將剩下的矩形棋盤繼續分割。

n-1 次分割後，可以得到 n 塊矩形棋盤。

假設原棋盤每一格都有一個分值，則分割後的每一塊都有一個總分，總分即爲所有格子分值之和。

設分割的每一塊棋盤總分爲 xi。

如何分割可以讓各矩形棋盤總分的均方差最小？

02 分析

先對均方差公式作一些簡化。

通過上面公式可以看出，其實就是要求分割後的 n 個矩形棋盤，分值平方的總和最小。

當你遇到一些沒有頭緒的問題的時候，先不要想太多，別上來整什麼高大上的思想，咱們就從最簡單的場景開始分析。

2.1 縮小問題規模

假設棋盤規模不是 88，而是 22。縮小問題規模是一種很有用的方法，因爲問題的本質並沒有發生變化，只是數據更小，就更有利於我們分析問題的本質。

2.2 開始分割

這時再讓你分割，還會覺得難嗎，全部手動枚舉也能解決啊。

先垂直切。

先水平切。

切 2 次，分割成 3 塊，總共也就 4 種情況，把每一種情況的方差算出來，選一個最小的就行了。

2.3 規律

每次分割有 2 種決策，要麼水平切，要麼垂直切。

針對一種決策，又有很多種具體的不同的切法。例如一個 4*4 的棋盤，先垂直切，就可以從 3 個不同的位置切。

如果給棋盤加一個座標，每一種切法就可以用一個線段來具體表示，比如用這條切線的兩個端點座標。

分割之後，就變成了 2 個更小的棋盤，而這 2 個棋盤也可以用矩形的座標表示，此時就把原問題變成了子問題，原問題的最優解也就是所有子問題中選一個最優的。

此時你可能會有幾個疑問：

  1. 爲什麼全局最優解可以轉化爲子問題的最優解呢？
    上面的分割方法，在每一個階段，我們已經把所有可能的分割方法全部枚舉完了，那其中的最優肯定就是當前階段的最優了，因爲沒有其它的可能性。

  2. 爲什麼當前階段的最優可以轉化爲下一階段？
    這就是一個無後效性，因爲我們只需要分割的分值平方和最小，並不關心它具體是怎麼分割的。之前怎麼分割，在當前階段看來都是一樣的，不受影響。

  3. 應該用幾維來表示狀態呢？這個就是到底要開幾維數組來遞推。上面無論是表示分割的線段，還是分割後的矩形，都至少要 2 個點座標，所以至少得 4 維。

03 建模

先垂直切，繼續切左邊或者右邊，找出最優解。

先水平切，繼續切上邊或者下邊，找出最優解。

當前輪次 t 只與上一次 t-1 有關，所以可以用 01 滾動數組，壓縮一維。

初始化的時候，所有小塊的獨立矩形棋盤都一次不切，所以就是矩形棋盤的分值平方。

04 代碼實現

定義

#define N 9
int chessboard[N][N];
int d[2][N][N][N][N];
int sum[N][N] = {0};

int getSum(int x, int y, int k, int l) {
    int ans = sum[k][l] - sum[k][y - 1] - sum[x - 1][l] + sum[x - 1][y - 1];
    return ans * ans;
}

int min(int x, int y) {
    return x < y ? x : y;
}

初始化

void init() {
  for (int i = 1; i <= 8; ++i) {
        for (int j = 1; j <= 8; ++j) {
            cin >> chessboard[i][j];
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + chessboard[i][j];
        }
    }
    for (int i = 1; i < N; ++i) {
        for (int j = 1; j < N; ++j) {
            for (int k = i; k < N; ++k) {
                for (int l = j; l < N; ++l) {
                    d[0][i][j][k][l] = getSum(i, j, k, l);
                }
            }
        }
    }
}

main

int main() {
    int n;
    cin >> n;
    init();
    int s = 0;
    for (int t = 1; t < n; ++t) {
        s = 1 - s;
        // 枚舉起點
        for (int i = 1; i < N; ++i) {
            for (int j = 1; j < N; ++j) {
                // 枚舉終點
                for (int k = i; k < N; ++k) {
                    for (int l = j; l < N; ++l) {
                        d[s][i][j][k][l] = 1e8;
                        // 橫切
                        for (int a = i; a < k; ++a) {
                            d[s][i][j][k][l] = min(d[s][i][j][k][l], d[1 - s][i][j][a][l] + getSum(a + 1, j, k, l));
                            d[s][i][j][k][l] = min(d[s][i][j][k][l], d[1 - s][a + 1][j][k][l] + getSum(i, j, a, l));
                        }
                        // 縱切
                        for (int b = j; b < l; ++b) {
                            d[s][i][j][k][l] = min(d[s][i][j][k][l], d[1 - s][i][j][k][b] + getSum(i, b + 1, k, l));
                            d[s][i][j][k][l] = min(d[s][i][j][k][l], d[1 - s][i][b + 1][k][l] + getSum(i, j, k, b));
                        }
                    }
                }
            }
        }
    }
    double average = sum[N - 1][N - 1] * 1.0 / n;
    double ans = d[s][1][1][8][8] * 1.0 / n - average * average;
    printf("%.3lf", sqrt(ans));
    return 0;
}

05 總結

動態規劃最重要的就是找出階段、狀態和決策，有時可以先用遞歸的方式建模，然後加記憶化優化，最後再轉爲遞推。

本文原創作者：小 K，一個思維獨特的寫手。
文章首發平臺：微信公衆號【小 K 算法】。

小 K 算法 曾就職華爲和美團，中山大學數學與計算機系本科，專注分享數學、算法、科學等硬核知識

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/1a_F2XVRcYdmBLSWxcWjeQ

猜你喜歡