สังเกตว่าการกระโดดจากช่อง $(n,n)$ ไปยังช่อง $(1,1)$ ในโจทย์ข้อนี้ จริง ๆ แล้วเราไม่จำเป็นต้องสนใจว่าเรากระโดดไปยังพิกัด $(r,c)$ ใดบ้าง แต่สนใจเพียงแค่ว่าช่องที่เรากระโดดไปมีค่า $r+c$ เป็นเท่าใด

จากเงื่อนไขโจทย์ เราต้องเริ่มจากค่า $2n$ แล้วกระโดดไปเรื่อย ๆ จนกว่าจะถึงค่า $2$ โดยการกระโดดแต่ละครั้งจะต้องกระโดดไปยังค่าที่น้อยหรือเท่ากับเสมอ และการกระโดดจากค่า $i$ ($r+c$) ไปค่า $j$ ($r'+c'$) ใด ๆ จะมีค่าใช้จ่ายเป็น $W_{i,j}$

เราสามารถมองเป็นปัญหา Shortest Path บนกราฟที่ประกอบไปด้วย $O(n)$ node และ $O(n^2)$ เส้นเชื่อม (สร้างกราฟตามที่อธิบายไว้ข้างต้น) ดังนั้น หากใช้ Dijkstra's Algorithm จะได้ Time Complexity เป็น $O(n^2 \log n)$

ทั้งนี้ เนื่องจากกราฟที่กำหนดให้เป็น Directed Graph เราสามารถใช้ Dynamic Programming แก้ได้ โดยนิยามให้ $dp_i$ เท่ากับค่าใช้จ่ายที่น้อยสุดที่เป็นไปได้เมื่อต้องเริ่มกระโดดจากค่า $i$ ไปยังค่า $0$ ซึ่งคำนวณได้ดังนี้

• $dp_2 = 0$
• สำหรับ $3 \leq i \leq 2n$ จะได้ $dp_i = \min\limits_{2 \leq j < i} \left( dp_j + W_{i,j} \right)$

คำตอบสุดท้ายอยู่ที่ $dp_{2n}$

วิธีนี้จะได้ Time Complexity เป็น $O(n^2)$

Implementation

ในภาษา C++:

#include <bits/stdc++.h>
using namespace std;

const int N = 310;
const int INF = 1e9;

int w[N * 2][N * 2];
int dp[N * 2];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= 2 * n; ++i) {
    for (int j = 1; j <= 2 * n; ++j) {
      scanf("%d", &w[i][j]);
    }
  }

  for (int i = 3; i <= 2 * n; ++i) {
    dp[i] = INF;
    for (int j = 2; j < i; ++j)
      dp[i] = min(dp[i], w[i][j] + dp[j]);
  }

  printf("%d", dp[2 * n]);
  return 0;
}