🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Quiz: DP on Grids and Strings: all 10 questions

Quiz: DP on Grids and Strings · Question 1 of 10

In unique paths (moves only right or down), why is dp[i][j] = dp[i − 1][j] + dp[i][j − 1]?

In unique paths (moves only right or down), why is dp[i][j] = dp[i − 1][j] + dp[i][j − 1]?

  1. A.Because the grid is square
  2. B.Every path into (i, j) arrives either from the cell above or from the cell on the left
  3. C.Because paths can go diagonally
  4. D.Because the first row is all zeros
Answer & explanation

Correct answer: Every path into (i, j) arrives either from the cell above or from the cell on the left

The two groups of paths do not overlap, so their counts add.

Can you get the rest right without peeking?

Take the timed Quiz: DP on Grids and Strings quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →