算法

(纯DP) $O(n^6)$

不难发现，X拔和n都是一个确数，因此我们的目的就在于如何切分。这里dp其实就是一种优雅的带记忆的切分。
其中dp[x1][y1][x2][y2][k]表示：
将矩阵(x1,y1)->(x2,y2)切割k次的最小方差。
其中的转移方程在第一个人的题解里写的即为详尽，这里就不再赘述。（第一人：心里没有一点AC数）
其实就是枚举切割方式，根据不同的切割方式，导出正确的式子即可。
写这篇主要是为了加深对纯dp写法和记忆化搜索写法的印象。
对于纯dp写法，最开始的初始化一定要做好，也就是状态的入口。另外，就是要注意前一个状态必须要先于现在状态推出，所以还要注意循环顺序。
而对于记忆化搜索，只要把f初始化成负数代表未被更新到即可，思路y总讲的很清晰了。

C++ 代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>

using namespace std ;

const int N = 9 , M = 15 ;
const double INF = 1e9 ;

double s[N][N] ;    //矩阵前缀和
int n;
double f[N][N][N][N][M] ;   
double X ;

//f[x1][y1][x2][y2][k] : 将矩阵(x1,y1)->(x2,y2)切割k次的最小方差

double get(int x1 , int y1 , int  x2 , int y2){
    double sum = s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1] ;
    sum -= X ;

    return sum * sum / n ;
}

void init()
{
    for(int x1 = 1 ; x1 < N ; x1++)
        for(int y1 = 1 ; y1 < N ; y1++)
            for(int x2 = x1 ; x2 < N ; x2++)
                for(int y2 = y1 ; y2 < N ; y2++)
                    for(int i = 0 ; i < M ; i++)
                        if( i )
                            f[x1][y1][x2][y2][i] = INF ;   //其他状态都没有到达
                        else
                            f[x1][y1][x2][y2][i] = get(x1,y1,x2,y2);    //切割0次
}

int main()
{
    cin >> n ; 
    for(int i = 1 ; i < N ; i++ )
        for(int j = 1 ; j < N ; j++ )
        {
            cin >> s[i][j] ;
            s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1] ; 
        }

    X = s[8][8]/n ;

    init() ;

    //注意，此时的k的循环必须写在外面
    //因为k-1层必须全部都先推出才可以
    //导致答案出错
    for(int k = 1 ; k < n ; k++ )
        for(int x1 = 1 ; x1 < N ; x1++)
            for(int y1 = 1 ; y1 < N ; y1++)
                for(int x2 = x1 ; x2 < N ; x2++)
                    for(int y2 = y1 ; y2 < N ; y2++)
                    {
                        if((x2-x1+1)*(y2-y1+1) < k) continue;   //无法砍这么多刀

                        double & v = f[x1][y1][x2][y2][k] ;

                        //横切
                        for(int i = x1 ; i < x2 ; i++ ){
                            v = min(v , f[x1][y1][i][y2][k-1] + get(i+1,y1,x2,y2) ) ;    //选上边,加下面
                            v = min(v , f[i+1][y1][x2][y2][k-1] + get(x1,y1,i,y2) ) ;    // 选下边
                        }

                        //纵切
                        for(int j = y1 ; j < y2 ; j++ ){
                            v = min(v , f[x1][y1][x2][j][k-1] + get(x1,j+1,x2,y2) ) ;    //选左边,加右边
                            v = min(v , f[x1][j+1][x2][y2][k-1] + get(x1,y1,x2,j) ) ;    // 选右边
                        }
                    }

    printf("%.3f\n" , sqrt(f[1][1][8][8][n-1]) ) ;
    return 0 ;
}

(记忆化搜索写法)

参考文献

y总的代码
f[x1][y1][x2][y2][k] : 将矩阵(x1,y1)->(x2,y2)分割成k个矩阵的最小方差

C++ 代码

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>

using namespace std ;

const int N = 9 , M = 15 ;
const double INF = 1e9 ;

double s[N][N] ;    //矩阵前缀和
int n;
double f[N][N][N][N][M] ;   
double X ;

double get(int x1 , int y1 , int  x2 , int y2){
    double sum = s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1] ;
    sum -= X ;

    return sum * sum / n ;
}

//记忆化搜索写法确实简便不少
//f[x1][y1][x2][y2][k] : 将矩阵(x1,y1)->(x2,y2)分割成k个矩阵的最小方差
double dp(int x1, int y1, int x2, int y2, int k)
{
    double &v = f[x1][y1][x2][y2][k];
    if (v >= 0) return v;
    if (k == 1) return v = get(x1, y1, x2, y2);

    v = INF;
    for (int i = x1; i < x2; i ++ )
    {
        v = min(v, get(x1, y1, i, y2) + dp(i + 1, y1, x2, y2, k - 1));
        v = min(v, get(i + 1, y1, x2, y2) + dp(x1, y1, i, y2, k - 1));
    }

    for (int i = y1; i < y2; i ++ )
    {
        v = min(v, get(x1, y1, x2, i) + dp(x1, i + 1, x2, y2, k - 1));
        v = min(v, get(x1, i + 1, x2, y2) + dp(x1, y1, x2, i, k - 1));
    }

    return v;
}

int main()
{
    cin >> n ; 
    for(int i = 1 ; i < N ; i++ )
        for(int j = 1 ; j < N ; j++ )
        {
            cin >> s[i][j] ;
            s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1] ; 
        }

    X = s[8][8]/n ;

    //记忆化搜索
    memset(f , -1 , sizeof f);
    printf("%.3f\n" , sqrt(dp(1,1,8,8,n)) ) ;

    return 0 ;
}