Cho ma trận 2D số nguyên dương. Từ (0,0) đến (n-1,n-1), tại (i,j) có thể nhảy đến (i, j+mat[i][j]) hoặc (i+mat[i][j], j). Tìm số bước nhỏ nhất. Ví dụ ma trận 3x3 → 2 bước.
Dùng quy hoạch động: DP[i][j] = 1 + min(DP[i+mat[i][j]][j], DP[i][j+mat[i][j]]).
Ví dụ
#include<iostream> #define N 3 using namespace std; int table[N][N]; bool temp_val[N][N]; int countSteps(int i, int j, int arr[][N]) { if (i == N - 1 and j == N - 1) return 0; if (i > N - 1 || j > N - 1) return INT_MAX; if (temp_val[i][j]) return table[i][j]; temp_val[i][j] = true; table[i][j] = 1 + min(countSteps(i + arr[i][j], j, arr), countSteps(i, j + arr[i][j], arr)); return table[i][j]; } int main() { int arr[N][N] = { { 2, 1, 2 }, { 1, 1, 1 }, { 1, 1, 1 } }; int ans = countSteps(0, 0, arr); if (ans >= INT_MAX) cout << -1; else cout <<"Number of steps: "<< ans; }
Kết quả
Number of steps: 2