MISERMAN - Wise And Miser
Jack is a wise and miser man. Always tries to save his money.
One day, he wants to go from city A to city B. Between A and B, there are N number of cities(including B and excluding A) and in each city there are M buses numbered from 1 to M. And the fare of each bus is different. Means for all N*M busses, fare (K) may be different or same. Now Jack has to go from city A to city B following these conditions:
- At every city, he has to change the bus.
- And he can switch to only those buses which have number either equal or 1 less or 1 greater to the previous.
You are to help Jack to go from A to B by spending the minimum amount of money.
N, M, K <= 100.
Line 1: N M
Line 2-: NxM Grid
Each row lists the fares the M busses to go form the current city to the next city.
Single Line containing the minimum amount of fare that Jack has to give.
Input: 5 5 1 3 1 2 6 10 2 5 4 15 10 9 6 7 1 2 7 1 5 3 8 2 6 1 9 Output: 10
1 -> 4 -> 1 -> 3 -> 1: 10
Submitted in java.AC in one go.
Recursion + Memoization did it for me :)
no dp only recursion
AC in one go :):) !!!!
AC in 1 go easy peasy dp
Same as problem "Philosophers stone" :)
Simple Bottom up algo can work for this.
Came here from the Philosopher's Stone problem..do try both. Great start for anyone starting out Dynamic Programming!
Simple Dp! AC in One Go!!!
c++(gcc4.3.2) doesn't work, careful