Grid Dynamic Programming

Question

atcoder.jp Problem Statement:

There is a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.

For each i and j (1≤i≤H, 1≤j≤W), Square (i,j) is described by a character \$a_{i,j}\$. If \$a_{i,j}\$ is ., Square (i,j) is an empty square; if \$a_{i,j}\$ is #, Square (i,j) is a wall square. It is guaranteed that Squares (1,1) and (H,W) are empty squares.

Taro will start from Square (1,1) and reach (H,W) by repeatedly moving right or down to an adjacent empty square.

Find the number of Taro's paths from Square (1,1) to (H,W). As the answer can be extremely large, find the count modulo 10⁹+7.

In short -
We have H×W grid with each element either '.' or '#' where # denote that we can't visit this block and '.' denote we can visit it. (1,1) and (H,W) will be always '.' . Find total no. of path from (1,1) to (H,W).

My approach

#include<iostream>
#include<vector>
using namespace std;

const int k=1000000007;

int sol(int i,int j,vector<vector<char>>v,int h,int w,vector<vector<int>>dp){
    if(i>h || j>w){
        return 0;
    }
    if(i==h && j==w){
        return 1;
    }
    if(v[i][j]=='#'){
        return 0;
    }
    if(dp[i][j]!=-1){
        return dp[i][j];
    }
    dp[i][j]=(sol(i+1,j,v,h,w,dp)%k + sol(i,j+1,v,h,w,dp)%k)%k;
    return dp[i][j];
}

int main(){
    int h,w;
    cin>>h>>w;
    vector<vector<char>>v(h);
    char c;
    vector<vector<int>>dp(h);
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>c;
            v[i].push_back(c);
            dp[i].push_back(-1);
        }
    }
    h--;
    w--;
    cout<<sol(0,0,v,h,w,dp)<<endl;
}

For below test case i am getting TLE

    20 20   
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................
    ....................

How I can improve the time complexity of my approach?

Answer 1

Understand argument passing

In the code below

int sol(int i,int j,vector<vector<char>>v,int h,int w,vector<vector<int>>dp){

you pass all arguments by value. This means that the compiler will generate deep copies of all the parameters. As you're calling this function repeatedly, this is very expensive for the vectors. However this means that the caller will not see any changes to the variables.

You should change these to pass by reference by changing to:

int sol(int i,int j, const vector<vector<char>>& v,int h,int w,vector<vector<int>>& dp){

This will avoid copying the vectors and save large amounts of execution time just in the copying. It will also protect the v vector from unintended mutations by passing by const reference.

Note that is this case, because you're creating copies of the dp vector instead of passing a reference to the same vector, the code below will always be false:

if(dp[i][j]!=-1){
    return dp[i][j];
}

Because at each call to sol you're getting a copy of the dp vector before anything was written to it. I.e. the dp vector will always be -1 everywhere at every point in the recursion. This means that this solution is actually not a dynamic programming solution but rather a depth first summing without the mnemonics that would make it a DP algorithm.

The code is computing in the opposite direction

You are actually computing the number of paths modulo K from the end to the start, and not the start to the end moving left and up. Instead of from start to end, moving right and left, the solution could be the same for may test cases but I'm not immediately convinced that this is always true.

White space

The code is devoid of most white space, while perfectly legal code that the compiler is happy to accept, it's very hard to read. I would much appreciate if you at the least added a space after , in argument and parameter lists. You could look into a tool such as clang-format that can automatically format your code prior to review. I don't want to prescribe a style as long as it's consistent and readable.

Improvement for performance

To be clear, the critical problem with the code as presented is that it is actually not reusing computational results because the DP matrix is passed by value. The secondary problem is that the other vectors are also copied at each recursion point which is unnecessarily slow.

First of we should use an iterative approach to filling in the DP matrix. This is possible because to fill in the first row, we only need elements from the left, and when filling in the next row the previous row and element is already available. This also means that in order to compute the result we only ever need two rows of the DP matrix, the current and the previous. An other interesting impact of filling in the DP matrix in this iterative way from left to right, top to bottom is that we do not actually need to store the maze layout, because we're processing it simultaneously to reading it in.

By carefully choosing sizes and starting conditions, we can write a very compact and efficient solution shown below. The code below computes the answer to test case number 4 in around 120 microseconds (ignoring the time it takes to print the result) on my computer and passes the other example test cases.

#include <algorithm>
#include <iostream>

const unsigned long k = 1000000007;
const unsigned long w_max = 1001;

int main() {
  unsigned long h, w;
  std::cin >> h >> w;

  // We allocate a contiguous array of longs on the stack.
  // We use long instead of int as long is guaranteed to be at least 32 bits
  // which can hold the result of k+k without truncating before we take the modulo,
  // while int is only guaranteed to be 16 bits (although it's 32 on PC).
  //
  // Allocating it on the stack as a fixed size avoids a slow memory and page allocation.
  // Note that we're over allocating the size here so that we can have an extra zero
  // padding before the actual DP matrix begins, this allows us to not have to check
  // for the left edge in the inner loop, avoiding a costly branch as long as this pad
  // is set to zero which it always will be as we never over write it.
  unsigned long dp[2 * (w_max + 1)] = {0};

  // We take two pointers into the above buffer so we can alternate them easily.
  unsigned long* dp_curr = &dp[0];
  unsigned long* dp_prev = &dp[w + 1];

  // This is the starting condition. It's stored in the dp_curr[1] (remember, 
  // after the pad) it'll then be swapped into dp_prev[1] when entering the loop
  // then when computing dp_curr[1] = dp_curr[0] + dp_prev[1] it'll be correctly
  // transfered to the starting square without additional branching in the inner loop.
  dp_curr[1] = 1;

  for (unsigned long i = 0; i < h; i++) {
    // Re-use old previous as new current and old current as new previous.
    // No need to clear the new current as we'll overwrite it below anyway
    // and we'll never access non-overwritten values.
    std::swap(dp_curr, dp_prev);
    for (unsigned long j = 1; j <= w; j++) {
      char c;
      std::cin >> c;
      if (c == '#') {
        dp_curr[j] = 0; // No ways to reach a wall
      } else {
        // This is where the magic happens. Because we use two rows and we initialized
        // both rows to 0, (ignoring the starting condition) then we do not need to
        // special case the first row to avoid out of bounds access.
        // In the same way, because we added a 0 padd to the left and start at j=1,
        // j-1 will always be valid and when j==1, dp_curr[j-1] is aways 0 thanks to
        // the pad, this again allows us to avoid bounds checking in the inner most loop.
        dp_curr[j] = (dp_curr[j - 1] + dp_prev[j]) % k;
      }
    }
  }
  // Of course, when we're done, the result is stored in the current DP row
  // at the last position and we need only to print it.
  std::cout << dp_curr[w] << std::endl;
}

I do believe that it will be hard to find a solution that is notably faster than the code presented above without doing something clever with I/O. It uses no dynamic memory (other than what iostreams and the runtime needs), and performs minimal branching and a good compiler could eliminate the inner branch totally and use conditional move if it makes sense.

Note for the curious, we use so little memory that everything will be permanently resident in the L1 data and instruction cache on the CPU and that there is so little branching that the CPU doesn't stall on misspredicted branches that often, this allows the very rapid computation of the result.