CODEWITHSUNDEEP
recursiondynamic-programmingcatalan
max12345
max12345

Reputation: 39

Writing recursive algorithm with dynamic programming

I want to write an algorithm using a dynamic programming technique, which does the following: Find number of monotonic paths along the edges of a grid with n × n square cells, which do not pass above the diagonal. A monotonic path is one which starts in the lower left corner, finishes in the upper right corner, and consists entirely of edges pointing rightwards or upwards.

I had some ideas, but can't figure out how to do it right.

Upvotes: 2

Views: 1004

Answers (3)

Learner
Learner

Reputation: 1

Let number of path reaching coordinate (i,j) be P(i,j). Therefore (assuming bottom left corner is (0,0)):

P(i,j) = P(i-1,j) + P(i,j-1)

You can further put conditions of coordinate not going below the diagonal. That is: i ranges from 0..n, j ranges from 0..n, but i<=j always.

Upvotes: 0

adl
adl

Reputation: 16044

Here is a possible recursion that considers only square grids.

There are two kinds of monotone paths over the n×n grid that do not cross the diagonal: those that touch the diagonal at some intermediate point (i,i) with 0 < i < n, and those that don't.

  • A path over the n×n grid that first touches the diagonal at (i,i) can be split in two: one path over the i×i grid that does not touch the diagonal, and another over the (n-i)×(n-i) grid and thay may touch the diagonal. This suggests that you can count those with a recursion that considers all possible i.

  • A path that does not touch the diagonal will start with "right", and end with "up". Between these two moves is a monotone path over a (n-1)×(n-1) grid that does not cross the diagonal but may touch it.

What we are computing here is the nth Catalan number. There is a formula for it if you want to verify your recursive computation.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726589

First, find a base for your recursion by solving a degenerate case (a 0 x 0 grid). Then look for a recurrence step by imagining that part of the problem, say, K x M is already solved, and see if you can expand upon that solution by adding one row or one column to it, making the solution K+1 x M or K x M+1. This should be simple: for each point you add, see if a grid point is below the diagonal, and then add up the number of paths leading to that point from the bottom and from the left. One of these points would be in the K x M, the other would be in the additional row or column that you are building.

With the degenerate case and a recursive step in hand, build your solution by first solving a 0 x N problem, then 1 x N, then 2 x N and so on, until you have your N x N solution.

Upvotes: 2

Related Questions