Open yokostan opened 5 years ago
Dynamic Programming beats 62%:
class Solution { public int minCost(int[][] costs) { int res = 0; if (costs == null || costs.length == 0 || costs[0].length == 0) return res; int n = costs.length; int[] dp0 = new int [n]; int[] dp1 = new int [n]; int[] dp2 = new int [n]; dp0[0] = costs[0][0]; dp1[0] = costs[0][1]; dp2[0] = costs[0][2]; for (int i = 1; i < n; i++) { dp0[i] = Math.min(dp1[i - 1] + costs[i][0], dp2[i - 1] + costs[i][0]); dp1[i] = Math.min(dp0[i - 1] + costs[i][1], dp2[i - 1] + costs[i][1]); dp2[i] = Math.min(dp0[i - 1] + costs[i][2], dp1[i - 1] + costs[i][2]); } res = Math.min(Math.min(dp0[n - 1], dp1[n - 1]), dp2[n - 1]); return res; } }
It only took me eight minutes to solve this, which kinda breaks my record~!
Dynamic Programming beats 62%:
It only took me eight minutes to solve this, which kinda breaks my record~!