given a directed graph,connected with n nodes , 1,2,…n. we need to tell number of ways to reach Nth node from 1st node. We need to memoize else TLE occurs. I am unable to think how to memoize. Pls help

Link:-problem

given a directed graph,connected with n nodes , 1,2,…n. we need to tell number of ways to reach Nth node from 1st node. We need to memoize else TLE occurs. I am unable to think how to memoize. Pls help

Link:-problem

1 Like

It’s a directed *acyclic* graph. That’s important.

If you want the number of ways to go to checkpoint i, it’s equal to the sum of the number of ways to get to the checkpoints that have a path to i. We don’t have to look forward because our graph is acyclic. Now once you calculate the paths, you just have to store it for later use.

2 Likes

Oh man! why does it never strike me… these ideas.

Thanks a lot BTW!