刷题4 剑指 Offer — 动态规划

剑指 Offer 10- I. 斐波那契数列

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xslxpr/
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

var fib = function(n) {
    let f0 = 0, f1 = 1, fn;
    if(n<2){
        return n
    }
    for(let i = 2; i<=n ;i++){
        fn = (f0 + f1) % 1000000007;
        f0 = f1;
        f1 = fn;
    }
    return fn
};

剑指 Offer 42. 连续子数组的最大和

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xsiyed/
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

var maxSubArray = function(nums) {
    let res = nums[0]
    for(let i = 1; i<nums.length ;i++){
        if(nums[i-1]>0){
            nums[i] += nums[i-1]
        }else{
            nums[i] = nums[i] 
        }
        res = Math.max(res,nums[i])
    }
    return res
};

剑指 Offer 47. 礼物的最大价值

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xstkx3/
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

var maxValue = function(grid) {
    let col = grid.length;
    let row = grid[0].length;
     for(let i = 0; i<col ;i++){
        for(let j = 0; j<row ; j++){
            if(i >= 1 && j >= 1){
                grid[i][j] += Math.max(grid[i-1][j],grid[i][j-1]);
            }else if(i >= 1){
                grid[i][j] += grid[i-1][j];
            }else if(j >= 1){
                grid[i][j] += grid[i][j-1];
            }
        }
    }
    return grid[col-1][row-1];
};

var maxValue = function(grid) {
    let col = grid.length;
    let row = grid[0].length;
       for(let i = 0; i<col ;i++){
        for(let j = 0; j<row ; j++){
             if(i == 0 && j==0){
                continue;
            }else if(i == 0){
                grid[i][j] += grid[i][j-1];
            }else if(j==0){
                grid[i][j] += grid[i-1][j];
            }else {
                grid[i][j] += Math.max(grid[i-1][j],grid[i][j-1]);
            }
        }
    }
    return grid[col-1][row-1];
};