C++で解く「最小下降経路の合計 II」― 動的計画法による効率的な解法

問題の概要

正方グリッド arr が与えられます。「非ゼロシフトの下降経路」とは、arr の各行からちょうど1つずつ要素を選び、かつ隣接する行で選んだ要素が同じ列にこないようにする選び方のことです。本問題では、このような下降経路の中で、選んだ要素の合計が最小となる値を求めます。

たとえば、入力が arr = [[1,2,3],[4,5,6],[7,8,9]] の場合、出力は 13 になります。考えられる下降経路は [1,5,9]、[1,5,7]、[1,6,7]、[1,6,8]、[2,4,8]、[2,4,9]、[2,6,7]、[2,6,8]、[3,4,8]、[3,4,9]、[3,5,7]、[3,5,9] の12通りです。このうち合計が最小となるのは [1,5,7] で、1 + 5 + 7 = 13 が答えとなります。

解法のアプローチ

各行の選び方をすべて試す全探索では計算量が膨大になります。そこで動的計画法（DP）を利用します。

セル (i, j) に到達するまでの最小合計を考えるとき、直前の行 (i-1) からは「同じ列以外」の任意の列から移動してきます。つまり arr[i][j] に加算すべき値は「前の行のうち j 列目を除いた部分の最小値」です。これを毎回 O(m) かけて求めると全体で O(n × m²) になりますが、接頭辞最小値（leftMin）と接尾辞最小値（rightMin）の2つの配列を前処理しておけば、各セルに対して O(1) で「同じ列を除く最小値」を求められ、計算量を O(n × m) に抑えられます。

アルゴリズムの手順

1. n を行数、m を列数とします。
2. i を 1 から n-1 まで、以下を繰り返します。
   • サイズ m の配列 leftMin と rightMin を用意します。
   • leftMin[0] := arr[i-1][0] とし、j を 1 から m-1 まで増やしながら leftMin[j] := min(leftMin[j-1], arr[i-1][j]) を計算します（左からの累積最小値）。
   • rightMin[m-1] := arr[i-1][m-1] とし、j を m-2 から 0 まで減らしながら rightMin[j] := min(arr[i-1][j], rightMin[j+1]) を計算します（右からの累積最小値）。
   • j を 0 から m-1 まで増やしながら、次の処理を行います。
     • leftVal := (j-1 ≥ 0 のとき leftMin[j-1]、それ以外は 1000000)
     • rightVal := (j+1 < m のとき rightMin[j+1]、それ以外は 1000000)
     • arr[i][j] := arr[i][j] + min(leftVal, rightVal)
3. ans := 無限大（INT_MAX）とします。
4. i を 0 から m-1 まで増やしながら、ans := min(ans, arr[n-1][i]) を計算します。
5. ans を返します。

理解を深めるために、以下の実装例を見てみましょう。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
int dp[10005][205];
class Solution {
   public:
   void pre(){
      for(int i = 0; i <= 10000; i++){
         for(int j = 0; j <=204; j++){
            dp[i][j] = -1;
         }
      }
   }
   int minFallingPathSum(vector<vector<int>>& arr) {
      int n = arr.size();
      int m = arr[0].size();
      for (int i = 1; i < n; i++) {
         vector<int> leftMin(m);
         vector<int> rightMin(m);
         leftMin[0] = arr[i - 1][0];
         for (int j = 1; j < m; j++) {
            leftMin[j] = min(leftMin[j - 1], arr[i - 1][j]);
         }
         rightMin[m - 1] = arr[i - 1][m - 1];
         for (int j = m - 2; j >= 0; j--) {
            rightMin[j] = min(arr[i - 1][j], rightMin[j + 1]);
         }
         for (int j = 0; j < m; j++) {
            int leftVal = (j - 1) >= 0 ? leftMin[j - 1] :
            1000000;
            int rightVal = (j + 1) < m ? rightMin[j + 1] :
            1000000;
            arr[i][j] += min(leftVal, rightVal);
         }
      }
      int ans = INT_MAX;
      for (int i = 0; i < m; i++)
      ans = min(ans, arr[n - 1][i]);
      return ans;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,2,3},{4,5,6},{7,8,9}};
   cout << (ob.minFallingPathSum(v));
}

入力

{{1,2,3},{4,5,6},{7,8,9}}

出力

13

計算量の評価

• 時間計算量： O(n × m) ― グリッドの各セルを定数回ずつ処理するためです。
• 空間計算量： O(m) ― leftMin と rightMin の2つの補助配列が必要です。

このように、接頭辞・接尾辞の累積最小値を活用することで、「同じ列を除外した最小値」の取得を定数時間にでき、大規模なグリッドに対しても効率的に最適解を求められます。