http://www.spoj.com/SPOJ/problems/ABCPATH/
Consider the above problem which can possibly have a maximum of 2500 letters.
It is a dp on graphs problem,solvable by dfs.
But I had this doubt
Let us consider using say ** dfs only** and not using any sort of DP. What is then the worst case time complexity of the dfs-solution. Expressed in terms of number of steps/letters traversed on the graph.
Solution with only dfs will work in O(h2·w2) time. Simple memorization will speed up it to O(h·w).
I understood with Memoization ,it would take O(h.w) steps.
How do you claim the only dfs complexity=O(h^2w^2)??Note that maximum path length=26=max(h)/2=max(w/2)
Like if there are 2 paths A1-B1-C-D-E and A2-B2-C-D-E ,(A1,A2 are As at different places)
traversing them by memoization would be (2)+(2)+(3) = 7 steps
whereas in case of ONLY DFS it would be (5)+(5) = 10 steps.
So How do You Find a tight bound on maximum number of steps without DP.
-Thanks
It's an asymtotic estimate. If u wanna to count maximum number of steps, I can't count it strictly. But can consider that it's about
. In such test:
I guess when dreamplay says about only dfs — he means full search without any pruning and memoization.
One can see that such solution works in O(2^(h + w)) on such case:
Here for most of paths for almost every cell on a path you'll have to check 2 possible moves.
I thought that DFS means at least information about visited vertices. And what you are talking about it's a brute. Isn't me right?
Actually, I guess it doesn't really matter, because we don't know what exactly author wants. But we described both cases, so we're fine anyway.
Thanks Lebron and Wackloner.
Yeah I meant the Lebron`s way.
Considering your pattern , also since I would stop at Z, and h<=50,w<=50 I get no. of dfs calls on A to be ~50.
Since for every A it would take O(2^26) thus giving O(50*2^26).
right?