Dynamic programming - Tree recursion with Memoization

Question

For the problem:

Consider an insect in an M by N grid. The insect starts at the bottom left corner, (0, 0), and wants to end up at the top right corner, (M-1, N-1). The insect is only capable of moving right or up. Write a function paths that takes a grid length and width and returns the number of different paths the insect can take from the start to the goal.

For example, the 2 by 2 grid has a total of two ways for the insect to move from the start to the goal. For the 3 by 3 grid, the insect has 6 diferent paths (only 3 are shown above).

Below is the recursive solution:

package main

import "fmt"

func paths(m, n int) int {

    var traverse func(int, int) int
    traverse = func(x, y int) int {

        if x >= m || y >= n {
            return 0
        }
        if x == m-1 && y == n-1 {
            return 1
        }
        return traverse(x+1, y) + traverse(x, y+1)
    }
    return traverse(0, 0)
}

func main() {
    fmt.Println(paths(1, 157))
}

As N increases, below is the effect:

fmt.Println(paths(1, 1)) // 1
fmt.Println(paths(2, 2)) // 2
fmt.Println(paths(3, 3)) // 6
fmt.Println(paths(4, 4)) // 20
fmt.Println(paths(5, 5)) // 70
fmt.Println(paths(6, 6)) // 252
fmt.Println(paths(7, 7)) // 924

Memoization can be applied in fibonacci problem, to reuse previous computations, using tree recursion

Does it make sense to memoiz this path problem? to reuse previous computations

(Note: this problem is meant to apply the idea of tree recursion, as mentioned here.)

@user2864740 Edited query with the answer for your question. But that does not decide, whether memoization can be used. Because there is no overlap/repetition on computations, because we need to find difeerent paths. — overexchange
– overexchange, Commented Aug 20, 2020 at 17:11
The problem is well known, and has a solution of (M+N-2 choose M-1) or equivalently (M+N-2 choose N-1). Does it make sense to use memoization which would take O(NM) time? Not really, since binomial coeffecients can be computed in O(min(M,N)) time with relatively simple code (for example big.NewInt(0).Binomial(M+N-2, M-1)) — Paul Hankin
– Paul Hankin, Commented Aug 20, 2020 at 17:22
@PaulHankin Why the problem statement is saying paths(3,3) is 3 but not 6? I see 6 paths. — overexchange
– overexchange, Commented Aug 20, 2020 at 17:29
There are only 3 paths (of the possible 6) shown in your diagram. That's all it's saying. — Paul Hankin
– Paul Hankin, Commented Aug 20, 2020 at 17:32

Paul Hankin · Accepted Answer · 2020-08-20 17:29:36Z

2

The problem is well known, and has a solution of (M+N-2 choose M-1) or equivalently (M+N-2 choose N-1). Does it make sense to use memoization which would take O(NM) time? Not really, since binomial coeffecients can be computed in O(min(M,N)) time (arithmetic operations) with relatively simple code.

For example (playground link):

package main

import (
    "fmt"
    "math/big"
)

func paths(n, m int) *big.Int {
    return big.NewInt(0).Binomial(int64(n+m-2), int64(m-1))
}

func main() {
    for i := 1; i < 10; i++ {
        fmt.Println(i, paths(i, i))
    }
}

answered Aug 20, 2020 at 17:29

Paul Hankin

58.8k11 gold badges99 silver badges125 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

overexchange Over a year ago

This problem is meant to apply the idea of tree recursion, as mentioend here

Armin Primadi · Accepted Answer · 2020-08-20 17:24:12Z

1

Yes, it's possible to use memoization. A key observation to make is consider a grid (1, 1) in a 3x3 grid:

(2, 0) (2, 1) (2, 2)

(1, 0) (1, 1) (1, 2)

(0, 0) (0, 1) (0, 2)

The number of paths in grid (1, 1) is equal to the number of paths from (1, 0) plus the number of paths from (0, 1) since there are only two possible ways one can arrive at path (1, 1).

Generalizing:

npath(x, y) = npath(x-1, y) + npath(x, y-1)

where npath(x, y) = the number of possible paths to visit grid (x, y)

Thus, if you build your recursion backwards you can apply memoization. By backwards I mean you have to start from the smaller case where npath(_, 0) = 1 and npath(0, _) = 1. underscore means any value.

A simple run of this algorithm leads to these number of paths in a 3x3 grid:

1 3 6

1 2 3

1 1 1

In fact, you can just do a double nested loop instead of a recursion as an optimization.

edited Aug 20, 2020 at 17:24

answered Aug 20, 2020 at 17:18

Armin Primadi

7646 silver badges10 bronze badges

4 Comments

overexchange Over a year ago

why should I start from (x,y). What is the advantage? In the above code, I started from (0,0)

Armin Primadi Over a year ago

for me it's just easier to think that way, but you can do the other way as well.

Armin Primadi Over a year ago

See my generalization in the comment. The idea in dynamic programming is usually to start with a smaller case. So think about smaller case first (i.e. grid 1x1, 1x2, 2x1, 2x2). Then figure out how to compute bigger case given a smaller case.

Armin Primadi Over a year ago

That is how you apply memoization naturally, once you have answer (memoize) for a smaller case, you can compute the larger case.

Collectives™ on Stack Overflow

Dynamic programming - Tree recursion with Memoization

2 Answers 2

1 Comment

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related