DP

by Krishna Ananthi

JavaScript

var coinChange = function(coins, amount) {
    let dp = new Array(amount+1).fill(amount+1);
    dp[0] = 0;
    for(let i=1;i<=amount;i++){
        for(let j=0;j<coins.length;j++){
            if(coins[j]<=i){
                dp[i] = Math.min(dp[i], 1+ dp[i-coins[j]]);
                console.log(dp)
            }
        }
    }
    return dp[amount] > amount ? -1: dp[amount]
};

//console.log(coinChange([1,3,5], 7));

var maxProduct = function(nums) {
    let n= nums.length, res = nums[0], prefix =0, suffix =0;
    for(let i=0;i<nums.length ;i++){
        prefix = nums[i]*(prefix ===0 ? 1: prefix);
        suffix = nums[n-i-1] *(suffix ===0 ? 1: suffix);
        res = Math.max(res,Math.max(prefix,suffix));
        console.log(prefix,suffix, res)
    } 
    return res == -0 ? 0 : res;
};
//console.log(maxProduct([-1,2,3,0,1,-2]))

function wordBreak(s, wordDict) {
        const dp = new Array(s.length + 1).fill(false);
        dp[s.length] = true;
			
        for (let i = s.length - 1; i >= 0; i--) {
            for (const w of wordDict) {
                if ( i + w.length <= s.length &&
                    s.slice(i, i + w.length) === w) {
                    dp[i] = dp[i + w.length];
                    
            				console.log(dp);
                }
                if (dp[i]) {
                
            console.log(dp);
                    break;
                }
            }
        }

        return dp[0];
    }
// console.log(wordBreak("applepenapple",  ["apple","pen","ape"]))

function lengthOfLIS(nums) {
        const LIS = new Array(nums.length).fill(1);

        for (let i = nums.length - 1; i >= 0; i--) {
            for (let j = i + 1; j < nums.length; j++) {
            console.log(LIS);
                if (nums[i] < nums[j]) {
                    LIS[i] = Math.max(LIS[i], 1 + LIS[j]);
                }
            }
        }
        return Math.max(...LIS);
    }
    
    console.log(lengthOfLIS( [9,1,4,2,3,3,7]))