source: https://leetcode.com/problems/minimum-costs-using-the-train-line/
A train line going through a city has two routes, the regular route and the express route. Both routes go through the same n + 1 stops labeled from 0 to n. Initially, you start on the regular route at stop 0.
You are given two 1-indexed integer arrays regular and express, both of length n. regular[i] describes the cost it takes to go from stop i – 1 to stop i using the regular route, and express[i] describes the cost it takes to go from stop i – 1 to stop i using the express route.
You are also given an integer expressCost which represents the cost to transfer from the regular route to the express route.
Note:
- There is no cost to transfer from the express route back to the regular route.
- You pay expressCost every time you transfer from the regular route to the express route.
- There is no extra cost to stay on the express route.
- a stop can be counted as reached from either route.
Return a 1-indexed array costs of length n, where costs[i] is the minimum cost to reach stop i from stop 0.
Input: regular = [1,6,9,5], express = [5,2,3,10], expressCost = 8
Output: [1,7,14,19]
Explanation:
- Take the regular route from stop 0 to stop 1, costing 1.
- Take the express route from stop 1 to stop 2, costing 8 + 2 = 10.
- Take the express route from stop 2 to stop 3, costing 3.
- Take the regular route from stop 3 to stop 4, costing 5.
The total cost is 1 + 10 + 3 + 5 = 19.
Note that a different route could be taken to reach the other stops with minimum cost.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Solution { public long[] minimumCosts(int[] regular, int[] express, int expressCost) { long[][] memo = new long[2][regular.length]; dfs(regular, express, regular.length-1, 0, 1, expressCost, memo); return memo[1]; } private long dfs(int[] regular, int[] express, int index, long sum, int isRegular, int expressCost, long[][] memo){ if(index<0){ return 0; } if(memo[isRegular][index]!=0){ return memo[isRegular][index]; } if(isRegular==1){ //either continue on the regular lane long a = regular[index] + dfs(regular, express, index-1, sum, 1, expressCost, memo); //or switch to the express lane long b = expressCost + express[index] + dfs(regular, express, index-1, sum, 0, expressCost,memo); memo[1][index] = Math.min(a, b); return memo[1][index]; }else { //either continue on the express lane long a = express[index] + dfs(regular, express, index-1, sum, 0, expressCost, memo); //or switch to the regular lane long b = regular[index] + dfs(regular, express, index-1, sum, 1, expressCost, memo); memo[0][index] = Math.min(a, b); return memo[0][index]; } } } |