Very Simple DP top-down solution:


  • 0
    S
    public int minCostClimbingStairs(int[] cost) {
            
            int[] mem = new int[cost.length];
            
            for (int i = 0; i < mem.length; i++) {
                mem[i] = Integer.MAX_VALUE;
            }
            
            int solution_1 = minCost(0, cost, mem);
            int solution_2 = minCost(1, cost, mem);
            
            return Math.min(solution_1, solution_2);
            
        }
        
        
        
        public int minCost(int i, int[] cost, int[] mem) {
            
            if (i >= cost.length)
                return 0;
            
            if (mem[i] == Integer.MAX_VALUE) {
                
                mem[i] = Math.min(cost[i] + minCost(i + 1, cost, mem), cost[i] + minCost(i + 2, cost, mem));
            }
            
            return mem[i];
            
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.