一、题意

给一个n行m列的整数矩阵（n<=10, m<=100），从第一列的任何一个位置出发，每次可以往→、↗、↘走一格，最终到达最后一列。矩阵时环形的，即第一行的上一行是最后一行，最后一行的下一行是第一行。现在要你找一条路线使得经过的数字之和最小。
打印出路径和最小和。
若有多解则输出字典序最小的。

二、解析

这是一道多阶段决策问题，一般这种问题都可以通过递推法的动态规划解决。

用dp[i][j]表示从a[i][j]开始的路径到达最后一列的最小和，的转移方程可以很容易得到：即dp[i][j]=a[i][j]+min(dp[→]，dp[↗]，dp[↘])。

这道题还要输出路径。这里主要复习一下通过递归打印路径的方法。这种方法的好处在于不需要维护新的存放路径信息的数组，直接利用dp[i][j]的关系来打印路径；当然会慢一点，但是不会影响时间复杂度，因此是我比较喜欢的方法（不用动脑就是好）。

三、代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn = 10 + 5, maxm = 100 + 5, INF = 1 << 30;
int n, m, a[maxn][maxm], dp[maxn][maxm];

void print_path(int i, int j) {
    if(j == m) return;
    if(j) cout << " ";
    cout << i + 1;

    vector<int> next = {(i - 1 + n) % n, i, (i + 1) % n};
    sort(next.begin(), next.end());
    for(auto ni : next) if(dp[ni][j + 1] + a[i][j] == dp[i][j]) {
        print_path(ni, j + 1);
        break;
    }
}

int main() {
    while(cin >> n >> m) {
        for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++) cin >> a[i][j];
        for(int i = 0; i < n; i ++) dp[i][m] = 0;
        for(int j = m - 1; j >= 0; j --) {
            for(int i = 0; i < n; i ++) {
                dp[i][j] = a[i][j] + min(dp[i][j + 1], min(dp[(i - 1 + n) % n][j + 1], dp[(i + 1) % n][j + 1]));
            }
        }
        int ans = INF, ans_idx = 0;
        for(int i = 0; i < n; i ++) if(dp[i][0] < ans) ans = dp[i][0], ans_idx = i;
        print_path(ans_idx, 0);
        cout << "\n" << ans << endl;
    }
}

四、归纳

  • 多阶段决策问题，可以使用动态规划来解决。
  • 通过递归来print_ans是一种比较方便的方法，因为它不需要额外维护存储路径信息的数组。