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 buses, 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.
Input
Line 1: N M
Line 2: N×M Grid
Each row lists the fares the M busses to go form the current city to the next city.
Output
Single Line containing the minimum amount of fare that Jack has to give.
Example
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
Explanation
1 → 4 → 1 → 3 → 1: 10
hide comments
soub5184:
2019-02-16 14:36:22
Submitted in java.AC in one go.
|
|
ashimk:
2019-01-07 20:55:56
Recursion + Memoization did it for me :)
|
|
amvi:
2018-11-08 11:34:18
no dp only recursion |
|
itssanat:
2018-10-26 22:02:45
AC in one go :):) !!!! |
|
masterchef2209:
2018-10-11 23:42:07
AC in 1 go easy peasy dp |
|
deepak097:
2018-08-11 23:53:22
Same as problem "Philosophers stone" :) |
|
roshan172:
2018-07-25 21:19:45
Simple Bottom up algo can work for this.
|
|
thisistia:
2018-06-26 11:49:21
Came here from the Philosopher's Stone problem..do try both. Great start for anyone starting out Dynamic Programming! |
|
vivek_rathi:
2018-03-26 11:50:43
Simple Dp! AC in One Go!!! |
|
richardks3647:
2018-03-03 08:16:22
c++(gcc4.3.2) doesn't work, careful |
Added by: | The quick brown fox jumps over the lazy dog |
Date: | 2010-10-18 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 NODEJS OBJC VB.NET |
Resource: | Udit Agarwal |