There are n stops on a journey. The train starts from station 0 and ends the journey at station n-1. All the ticket costs are given in an array. You must find the minimum cost to reach the destination.
​Input: int[][] cost = {{0, 25, 70, 85}, {INF, 0, 35, 45}, {INF, INF, 0, 65}, {INF, INF, INF, 0} }; static int INF = Integer.MAX_VALUE; Output: 70 Explanation: To get the minimum cost, first you will have to go from station 0 to 1 for cost 25, then from station 1 to the last one for cost 45. This means a total cost of 70. |
Solution:
1. static int minimumCost(int[][] cost) { 2. int size = cost.length; 3. int[] minimumCosts = new int[size]; 4. for (int i = 1; i < size; i++) { 5. minimumCosts[i] = Integer.MAX_VALUE; 6. } 7. 8. for (int i = 0; i < size; i++) { 9. for (int j = i + 1; j < size; j++) { 10. if (minimumCosts[j] > minimumCosts[i] + cost[i][j]) { 11. minimumCosts[j] = minimumCosts[i] + cost[i][j]; 12. } 13. } 14. } 15. 16. return minimumCosts[size - 1]; 17. } 18.