动态规划

[AILINGANGEL]

1.爬楼梯

一次可以爬1步或者2步，爬到n层有几种方法

核心思想: 每次爬楼梯可以爬一层或者两层，那么爬到n层应该是Step[n-1]爬到n-1层的方法加上Step(n-2)爬到n-2层的方法

Step[n] = Step[n-1] + Step[n-2];

// step[n]表示爬到n层有多少种方法
var climbStairs = function(n) {
    //初始化爬到0层就是不动一种方法，爬到一层只能跨一步，一种方法
    let step = [1, 1];
    for(let i = 2; i <= n; i++){
        step[i] = step[i - 1] + step[i - 2];
    }
    return step[step.length - 1];
};

2. Fibonacci Number

F(0) = 1, F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.

// 动态规划
var fib = function(N) {
    let ans = [1, 1];
    for(let i = 2; i < N+ 1; i++) {
        ans[i] = ans[i-1] + ans[i-2];
    }
    return ans[N]
};

// 递归
var fib = function(N) {
    if(N < 2) {
        return N;
    }
    return fib(N-1) + fib(N-2);
};

3.买卖股票的最佳时机

核心思想，记录到目前为止最低的价格，然后对比不卖当前股票的利润和卖当前股票的利润
maxProfit[i] = Math.max( maxProfit[i - 1], price[i] - minPrice);
maxProfit[i]表示第i天卖掉股票的最大利润

// 迭代解法
var maxProfit = function(prices) {
    let min = Number.MAX_VALUE;
    let profit = 0;
    for (let i = 0; i < prices.length; i++) {
        if (prices[i] < min) {
            min = prices[i];
        } else if (prices[i] - min > profit) {
            profit = prices[i] - min;
        }
    }
    return profit;
};

var maxProfit = function(prices) {
    let arr = [0];
    let min = prices[0];
    for (let i = 1; i < prices.length; i++) {
        arr[i] = Math.max(arr[i - 1], prices[i] - min);
        if (prices[i] < min) {
            min = prices[i];
        }
    }
    return arr[arr.length - 1];
};

4.rob house

核心思想： ans[i]表示偷第i间房子的钱，如果头第i间房子的钱就不能偷第i-1间房子的；
ans[i] = Math.max(ans[i-1], ans[i - 2] + nums[i])

var rob = function(nums) {
    if(nums.length === 0) return 0;
    let ans = [nums[0]];
    for(let i = 1; i < nums.length; i++){
        ans[i] = Math.max(nums[i] + (ans[i-2] ? ans[i-2] : 0), ans[i-1]);
    }    
    return ans[ans.length - 1];
};