Dynamic programming beautiful questions

by rishul matta

HTML

https://leetcode.com/problems/climbing-stairs/solution/

https://leetcode.com/problems/min-cost-climbing-stairs/submissions/

https://leetcode.com/problems/house-robber/submissions/

JavaScript

/**
 * @param {number[]} cost
 * @return {number}
 this is the bottom up implementation and this doesnt require a recursion it is basically a loop and can be very easily solved by using just a loop
 
 missed the case of [0, 1, 2, 2]
 */
var minCostClimbingStairs = function(cost) {
    if (cost.length === 1) {
        return cost[0];
    }
    const memo = [
        cost[0],
        cost[1]
    ];
    
	const recurse = (index) => {
		if (index === cost.length) {
                // one can go to last index or skip the last index via last but one index
        		return Math.min(memo[memo.length - 1], memo[memo.length - 2]);
  		}
		
        let costOfInd = (cost[index] || 0) + Math.min(memo[index - 1], memo[index - 2]);

		memo.push(costOfInd);
		return recurse(index + 1);
    }

	return recurse(2);
};




/**
 * @param {number[]} cost
 * @return {number}
 
 below is the top down approach of the question
 */
var minCostClimbingStairs = function(cost) {
    if (cost.length === 1) {
        return cost[0];
    }
    const memo = {
        0: cost[0],
        1: cost[1]
};
    
	const recurse = (index) => {
		if (memo[index] !== undefined) {
            return memo[index];
        }
        
        if (index >= 2) {
            const optimised = Math.min(recurse(index - 1), recurse(index - 2));
            memo[index] = optimised + (cost[index] || 0);
            
            return memo[index];
        }
        
        console.log(index)

    }

	return Math.min(recurse(cost.length), recurse(cost.length - 1));
};