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!