带行使用限制的二维数组最低成本路径求解，如何优化递归算法？

我最近在求职面试中遇到了一个类似问题，现有解法复杂度太高，一直没能找到更高效的实现方案。

问题规则 #

默认沿x轴从左向右移动，约束如下：

• 每次移动必须向右行进1个索引位
• 可任选任意一行作为起点
• 一旦离开某行后，不得再次返回使用该行
• 切换行时可选择任意未使用过的行
  目标是找到从数组最左侧到最右侧的最低成本通行路径。

示例 #

输入数组:
{
  {920, 239, 191, 267, 166, 879, 791, 998, 447,  617, 31,  169},
  {361, 516, 506, 279, 406, 231, 828, 410, 408,  199, 507, 671},
  {143, 69,  675, 847, 871, 704, 471, 796, 1000, 711, 42,  380},
  {559, 407, 555, 390, 672, 415, 902, 570, 803,  29,  394, 937},
  {407, 336, 427, 801, 509, 803, 267, 617, 47,   710, 529, 423},
  {377, 26,  561, 950, 134, 343, 542, 342, 549,  65,  39,  900}
}

输出结果: 2634
对应路径: 143, 69, 506, 279, 134, 343, 542, 342, 47, 29, 31

现有实现（C++） #

#include <iostream>
#include <algorithm>
#include <list>
#include <sstream>
#include <set>
#include <climits>

namespace stack_overflow_example {

    int const x_dim = 6;
    int const y_dim = 12;
    int expected = 2634;

    int arr[x_dim][y_dim] =
            {
                    {920, 239, 191, 267, 166, 879, 791, 998, 447,  617, 31,  169},
                    {361, 516, 506, 279, 406, 231, 828, 410, 408,  199, 507, 671},
                    {143, 69,  675, 847, 871, 704, 471, 796, 1000, 711, 42,  380},
                    {559, 407, 555, 390, 672, 415, 902, 570, 803,  29,  394, 937},
                    {407, 336, 427, 801, 509, 803, 267, 617, 47,   710, 529, 423},
                    {377, 26,  561, 950, 134, 343, 542, 342, 549,  65,  39,  900}
            };

    int minimumValue = INT32_MAX;

    void recursive_function(int x, int y, int value, std::set<int> unusedX) {
        int summed = value + arr[x][y];
        if (summed > minimumValue) {
            return;
        }
        if ((y + 1) < y_dim) {
            recursive_function(x, y + 1, summed, unusedX);
            unusedX.erase(x);
            for (auto const &i: unusedX) {
                recursive_function(i, y + 1, summed, unusedX);
            }
        } else {
            minimumValue = minimumValue < summed ? minimumValue : summed;
        }
    }

    void calculate() {
        std::set<int> unusedX;
        for (int i = 0; i < x_dim; i++) {
            unusedX.emplace(i);
        }
        for (int i = 0; i < x_dim; i++) {
            recursive_function(i, 0, 0, unusedX);
        }
        std::cout << "Expected was: " << expected << " received " << minimumValue;
    }

}

int main() {
    stack_overflow_example::calculate();
}

问题说明 #

上述递归回溯解法运行结果正确，但时间复杂度过高，当数组规模达到[12][24]时运行时间已经无法接受，需要更高效的实现方案，编程语言不限。 #

优化方案 #

核心思路：状态压缩动态规划 #

因为行数最多为12，可以用位掩码表示已经使用过的行集合，总状态量可控：

状态定义

dp[y][mask][last]：走到第y列、已使用行的位掩码为mask、当前所在行是last时的最小路径成本。
其中mask的第i位为1表示第i行已经被使用过，不能再切换回去。

状态转移

1. 不切换行：直接走到下一列同一行：

dp[y+1][mask][last] = min(dp[y+1][mask][last], dp[y][mask][last] + arr[last][y+1])

2. 切换行：选择任意未被使用的行next，更新掩码后走到下一列的next行：

new_mask = mask | (1 << next)
dp[y+1][new_mask][next] = min(dp[y+1][new_mask][next], dp[y][mask][last] + arr[next][y+1])

初始状态

所有行都可以作为起点，因此对任意行i：

dp[0][1 << i][i] = arr[i][0]

最终结果

遍历所有mask和last，取dp[y_dim - 1][mask][last]的最小值即可。

复杂度分析 #

假设行数为n，列数为m：

• 总状态数：m * 2^n * n，当n=12, m=24时，总状态量为24 * 4096 * 12 = 1,179,648，完全在可接受范围内
• 每个状态转移的时间复杂度为O(n)，总时间复杂度为O(m * n^2 * 2^n)，对于n=12, m=24的场景运行速度极快

参考C++实现 #

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main() {
    int x_dim = 6, y_dim = 12;
    int arr[6][12] = {
        {920, 239, 191, 267, 166, 879, 791, 998, 447,  617, 31,  169},
        {361, 516, 506, 279, 406, 231, 828, 410, 408,  199, 507, 671},
        {143, 69,  675, 847, 871, 704, 471, 796, 1000, 711, 42,  380},
        {559, 407, 555, 390, 672, 415, 902, 570, 803,  29,  394, 937},
        {407, 336, 427, 801, 509, 803, 267, 617, 47,   710, 529, 423},
        {377, 26,  561, 950, 134, 343, 542, 342, 549,  65,  39,  900}
    };
    // 初始化dp数组，填充无穷大
    vector<vector<vector<int>>> dp(y_dim, vector<vector<int>>(1<<x_dim, vector<int>(x_dim, INT_MAX)));
    for(int i = 0; i < x_dim; i++) {
        dp[0][1<<i][i] = arr[i][0];
    }
    // 遍历每一列
    for(int y = 0; y < y_dim -1; y++) {
        for(int mask = 0; mask < (1<<x_dim); mask++) {
            for(int last = 0; last < x_dim; last++) {
                if(dp[y][mask][last] == INT_MAX) continue;
                // 情况1：不换行
                dp[y+1][mask][last] = min(dp[y+1][mask][last], dp[y][mask][last] + arr[last][y+1]);
                // 情况2：换行
                for(int next = 0; next < x_dim; next++) {
                    if(mask & (1<<next)) continue; // next行已被使用，跳过
                    int new_mask = mask | (1<<next);
                    dp[y+1][new_mask][next] = min(dp[y+1][new_mask][next], dp[y][mask][last] + arr[next][y+1]);
                }
            }
        }
    }
    // 找最后一列的最小值
    int ans = INT_MAX;
    for(int mask = 0; mask < (1<<x_dim); mask++) {
        for(int i = 0; i < x_dim; i++) {
            ans = min(ans, dp[y_dim-1][mask][i]);
        }
    }
    cout << "最小成本为：" << ans << endl; // 输出2634，和示例一致
    return 0;
}

如果需要还原路径，只需要在dp转移时额外记录每个状态的前驱信息，最后反向回溯即可得到完整路径。 #

内容的提问来源于stack exchange，提问作者Redouane Elghazi