这个是最近看到的一道题，题目有些长，我这里把题目的背景省略掉了，只是写题目需要我们求解什么， 以及我们应该如何求解它。

题目的意思是这样的：

说有一个由 0 和 1 组成的二维数组，每一行都有至少一个 1。每一行可以左右移动，现在问我们最少需要 移动几次可以使数组中的一列全为 1。

为了方便理解，我们在这里举个例子。如下列的二维数组：

1 0 0 0
0 0 0 1
1 0 0 0

为了让数组中的一列全为 1，我们可以把第二行向左移动 3 格，变成这样：

      1 0 0 0
0 0 0 1
      1 0 0 0

然后我们也可以证明，3 也是能够满足题意所需的最少移动的步数。

为了解决这个问题，我们可以利用动态规划的方法去求解。我们复习一下，动态规划方法有两个元素，一个是 数组，用来存放所有解决问题的局部解；另一个是公式，用来填满整个数组。现在，我们先来定义这个数组。

我们采用求什么就定义什么的方法，我们现在求解二维数组 a[m][n] 需要移动多少次可以使一列全为 1，那么如果我们 把每一列为 1 所需要移动的最少次数求出来，那么它们之中的最小值就是我们的答案；现在问题转化为如何 求解每一列为 1 所需要移动的最少次数。我们想一下，如果我们对于数组中的任意一个元素 a[i][j]，我们 可以知道它为 1 所需要移动的最少次数 s[i][j]，那么对于第 j 列来说，我们只需要将 s[0][j] ~ s[m-1][j] 的所有元素相加就可以得到每一列为 1 所需要移动的最少次数，从而将题目解决。所以我们第一步就是定义一个 和原二维数组一样大的数组 s[m][n]。

好，现在我们数组定义好了，接下来，我们来思考如何把这个数组填满。这个问题可以分为两种情况讨论，第一 种情况，当 a[i][j] == 1 时，因为 s[i][j] 为 a[i][j] 为 1 的最小移动次数，所以 s[i][j] 为 0；第二种 情况，当 a[i][j] != 1 时，此时 s[i][j] 就应该等于它左边的一个数加上 1，即 s[i][j-1] + 1。第二种情况是 s[i][j] 和 s[i][j-1] 的关系，所以我们首先需要求出第一列的值，保证无论是第一种情况还是第二种情况，都 可以填充上具体的值。对于第一列的值，如果 a[i][j] == 1，那么 s[i][j] = 0；反之，s[i][j] = MAX（MAX 代表 一个不可达的最大值，我们在这里可以将 MAX 赋值为 n，即原数组的列宽）。这样我们就可以将 s[m][n] 填满了。 但是，这样做显然得不到最优的结果，因为还存在这样一种情况，即如果存在一行，a[i][0] ~ a[i][n-2] 都 是 0，那么 s[i][0] ~ s[i][n-2] 的值就是 MAX ~ MAX+n-2；a[i][n-1] 是 1，则 s[i][n-1] 的值为 0。此时显然 s[i][0] ~ s[i][n-2] 都是可以为 1 的，所以需要从右到左修正一下，修正的结果为从 s[i][0] ~ s[i][n-2] 的值依次 为 n-1 ~ 1。所以，每当我们从左到右计算完一行之后，我们都需要从右到左再检查一下，检查的逻辑为，当 s[i][j] > s[i][j+1] + 1 时， s[i][j] = s[i][j+1] + 1。

当我们把整个 s[m][n] 填写完成之后，我们将每列的值相加，然后从中取最小值即可。这样，我们就可以把整个问题 解决了。接下来，我们给出 C 语言的实现代码：

#define MAX 1000
int GetMinMovesNum(int **a, int size, int *aColSize)
{
    int colSize = aColSize[0];
    int s[size][colSize];
    int i, j;
    int min, res;

    for (i = 0; i < colSize; i++) {
        if (a[0][i] == 1) {
            s[0][i] = 0;
            continue;
        }
        s[0][i] = MAX;
    }

    for (i = 0; i < size; i++) {
        for (j = 1; j < colSize; j++) {
            if (a[i][j] == 1) {
                s[i][j] = 0;
                continue;
            }
            s[i][j] = s[i][j-1] + 1;
        }

        for (j = colSize - 2; j >= 0; j--) {
            if (s[i][j] > s[i][j+1] + 1) {
                s[i][j] = s[i][j+1] + 1;
            }
        }
    }

    min = MAX * MAX;
    res = 0;
    for (j = 0; j < colSize; j++) {
        for (i = 0; i < size; i++) {
            res += s[i][j];
        }
        if (min > res) {
            min = res;
        }
    }
    return min;
}

以上。