Tìm số đường đi với số lần rẽ nhiều nhất là k

Nguồn:  http://www.geeksforgeeks.org/count-number-of-paths-with-k-turns/
Bài viết này chỉ là dịch thô từ nguồn trên do khả năng của mình có hạn nên rất mong nhận được sự góp ý từ các bạn

Cho một ma trận "m x n", tìm số đường đi để đến được phần tử thứ (i,j) từ phần tử thứ (0,0) với số lần rẽ tối đa là k

Rẽ là gì? Đơn giản nếu bạn đang đi theo hàng mà lại đột ngột đi theo cột thì đó là mọt lân rẽ

Nhớ rằng bạn chỉ được đi sang phải và xuống dưới mà thôi.

Ví dụ: 

Input:  m = 3, n = 3, k = 2
Output: 4
Nhìn đồ thị phía dưới.

Input:  m = 3, n = 3, k = 1
Output: 2 

Nguồn: http://qa.geeksforgeeks.org/1993/no-of-paths-with-k-turns

Chúng tôi đề nghị bạn hãy tự nghĩ cách giải quyết trước khi xem lời giải

Hãy xem công thức đệ quy sau :

countPaths(i, j, k): đếm số đường đi có thể có đến (i,j) từ (0, 0)
countPathsDir(i, j, k, 0): đếm số đường đi có thể có đến (i, j) 
                           nếu đi dọc theo dòng. 
countPathsDir(i, j, k, 1): đếm số đường đi có thể có đến (i, j)                            nếu đi dọc theo cột. 
biến thứ 4 của countPathsDir() chỉ đường chúng ta sẽ đi (dòng hoặc cột).

Giá trị của countPaths() có thể tính theo công thức:
countPaths(i, j, k) = countPathsDir(i, j, k, 0) + 
                      countPathsDir(i, j, k, 1) 

Và giá trị của  countPathsDir() có thể xác định theo công thức đệ quy:

// Trường hợp cơ bản

// Nếu đường đi hiện tại đang là đi theo dòng
If (d == 0) 
  // Count paths for two cases
  // 1) We reach here through previous row.
  // 2) We reach here through previous column, so number of 
  //    turns k reduce by 1.
  countPathsDir(i, j, k, d) = countPathsUtil(i, j-1, k, d) +
                              countPathsUtil(i-1, j, k-1, !d);

// Nếu đường đi hiện tại đang là đi theo cột
Else 
  // Giải quyết tương tự
  countPathsDir(i, j, k, d) =  countPathsUtil(i-1, j, k, d) +
                               countPathsUtil(i, j-1, k-1, !d);

Chúng ta có thể giải quyết vấn đề này bằng cách sử dụng quy hoạch động với độ phức tạp là một đa thức. Ý tưởng là sử dụng một mảng 4 chiều dp[m][n][k][d] với m là index của dòng, n là index của cột, k là số đường rẽ tối đa và d để đánh dấu đồng đi.

Dưới đây là phần code cài đặt bàng java.

public class Count_number_of_paths_with_at_most_k_turns {

final int MAX = 100;

// table to store to store results of subproblems

int dp[][][][] = new int[MAX][MAX][MAX][2];

// Returns count of paths to reach (i, j) from (0, 0)

// using at-most k turns. d is current direction

// d = 0 indicates along row, d = 1 indicates along

// column.

int countPathsUtil(int i, int j, int k, int d) {

// If invalid row or column indexes

if (i < 0 || j < 0)

return 0;

// If current cell is top left itself

if (i == 0 && j == 0)

return 1;

// If 0 turns left

if (k == 0) {

// If direction is row, then we can reach here

// only if direction is row and row is 0.

if (d == 0 && i == 0)

return 1;

// If direction is column, then we can reach here

// only if direction is column and column is 0.

if (d == 1 && j == 0)

return 1;

return 0;

}

// If this subproblem is already evaluated

if (dp[i][j][k][d] != -1)

return dp[i][j][k][d];

// If current direction is row, then count paths for two cases

// 1) We reach here through previous row.

// 2) We reach here through previous column, so number of

// turns k reduce by 1.

if (d == 0)

return dp[i][j][k][d] = countPathsUtil(i, j - 1, k, d) + countPathsUtil(i - 1, j, k - 1, 1 - d);

// Similar to above if direction is column

return dp[i][j][k][d] = countPathsUtil(i - 1, j, k, d) + countPathsUtil(i, j - 1, k - 1, 1 - d);

}

// This function mainly initializes 'dp' array as -1 and calls

// countPathsUtil()

int countPaths(int i, int j, int k) {

// If (0, 0) is target itself

if (i == 0 && j == 0)

return 1;

// memset

for (int first = 0; first < MAX; first++) {

for (int second = 0; second < MAX; second++) {

for (int third = 0; third < MAX; third++) {

dp[first][second][third][0] = -1;

dp[first][second][third][1] = -1;

}

}

}

// Recur for two cases: moving along row and along column

return countPathsUtil(i - 1, j, k, 1) + // Moving along row

countPathsUtil(i, j - 1, k, 0); // Moving along column

}

// Driver program

public static void main(String[] args) {

Count_number_of_paths_with_at_most_k_turns test = new Count_number_of_paths_with_at_most_k_turns();

int m = 2, n = 2, k = 2;

System.out.println("Paths: " + test.countPaths(m - 1, n - 1, k));

}

}