Help with basic dp!!

general
, ,
1

So i came across this question link text and I at my first sight was trying to solve it using combinatorics but eventually I was unable to figure out the answer… Well I am totally newbie to dp and I am like still practising the easy questions on dp… In accordance to that I wrote this code for the same problem

link text
I am getting a WA so when i turned to all solutions , they all are doing it with declaring two 2D arrays…
I dont know why is there some advantage of using them… And I have tried doing it with a single one…

My code marks all dp[0][j] 0<=j<=n and dp[i][0]=0 0<=i<=m and all other elements -1 …
I then mark all the blockings with 0… Then

 if(dp[i][j]!=0)

{
dp[i][j]=dp[i][j]%mod+dp[i-1][j]%mod+dp[i][j-1]mod+1; dp[i][j]=mod;
}

for all i,j starting from 1…
Can you tell whhy the code fails

2

Your code marks all dp[0][i]=0. Consider this path, when you have to go from 0,0 to 0,1. You have a path. A single path. Similarly, for all dp[0][i] and dp[i][0], you have a path, and only a single path, assuming no cell is of type 0,i or i,0 is blocked.

Now, if suppose you have to go from 0,0 to 0,3 but the cell 0,1 is blocked. You can never reach 0,3 now since you can move only down or right. So, if any cell of type 0,i is blocked, all cells of type 0,j where j>=i will be 0 since they cannot be reached now.
The rest is correct I suppose.

Here: http://ideone.com/JAg3B5

3

No dude my grid is (1,1)->(n,m) i.e. I am using base indexing 1 but ii have marked all the columns of 0 th index as zero because i can use this always { dp[i][j]=dp[i][j]%mod+dp[i-1][j]%mod+dp[i][j-1]mod+1; dp[i][j]=mod; }

4

well whatever I was able to find a bug thanx to you :slight_smile: … Moover you showed it can be done with a single table… The fact is I fear dp so much … Its like a hype but eventually I am like it was easy :smiley:

5

Glad to help :slight_smile: