第八天华为机考练习（JavaScript）（动态规划练习）

注：华为机试和剑指offer的JavaScript Node的书写方式不同，剑指offer只需学核心代码然后return，华为机试需要自写输入输出，输出console就行。leetcode用js不用考虑输入输出。

1. leetcode70. 爬楼梯

https://leetcode.cn/problems/climbing-stairs/

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

/**

 * @param {number} n

 * @return {number}

 */

var climbStairs = function(n) {

    // 动态规划f(n)=f(n-1)+f(n-2)

    let arr=[]

    arr[0]=1

    arr[1]=2

    for(let i=2;i<n;i++){

        arr[i]=arr[i-1]+arr[i-2]

    }

    return arr[n-1]

};

2.leetcode121.买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

/**

 * @param {number[]} prices

 * @return {number}

 */

var maxProfit = function(p) {

    //1. 暴力解法：超时了

    // let profit=0

    // for(let i=0;i<p.length-1;i++){

    //     for(let j=i+1;j<p.length;j++){

    //         let dec=p[j]-p[i]

    //         profit=dec>profit?dec:profit

    //     }

    // }

    // return profit

    //2. 一次遍历（贪心算法，因为都希望在最低的时候买入）:通过（最优）

    let cost=p[0]

    let profit=0

     for(let j=1;j<p.length;j++){

         let dec=p[j]-cost

        dec<0?cost=p[j]:profit=Math.max(profit,dec)

    }

    return profit

    // 3. 动态规划（动态规划是定义数组进行递推）：通过

    // let dp=[]//里面存放到当天为止的最大收益

    // let cost=p[0]

    // dp[0]=0//第一天当天为止最大收益

    // for(let i=1;i<p.length;i++){

    //     dp[i]=Math.max(dp[i-1],p[i]-cost)

    //     cost=Math.min(cost,p[i])

    // }

    // return dp[p.length-1]

};

3.leetcode198.打家劫舍

https://leetcode.cn/problems/house-robber/

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

/**

 * @param {number[]} nums

 * @return {number}

 */

var rob = function(nums) {

    //1. 动态规划：f(n)=max(f(n-1),f(n-2)+nums[n])

    // let dp=[]

    // dp[0]=nums[0]

    // dp[1]=Math.max(nums[0],nums[1])

    // for(let i=2;i<nums.length;i++){

    //     dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i])

    // }

    // return dp[nums.length-1]

    //2. 动态规划的空间优化：f(n)=max(f(n-1),f(n-2)+nums[n]),不用数组存整个过程，只用两个变量存当前和前一个

    let pre=0,cur=0

    for(let i=0;i<nums.length;i++){

        let cur1=Math.max(cur,pre+nums[i])

        pre=cur

        cur=cur1

    }

    return cur

};

4.leetcode213打家劫舍II

https://leetcode.cn/problems/house-robber-ii/submissions/

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

/**

 * @param {number[]} nums

 * @return {number}

 */

var rob = function(nums) {

    //动态规划：条件是偷第一家或偷最后一家的总的偷盗金额,后面动态规划部分和198题一样

    function rob(arr){

        let dp=[]

        dp[0]=arr[0]

        dp[1]=Math.max(arr[0],arr[1])

        for(let i=2;i<arr.length;i++){

            dp[i]=Math.max(dp[i-1],dp[i-2]+arr[i])

        }

        return dp[arr.length-1]

    }

    if(nums.length===1) return nums[0]

   return Math.max(rob(nums.slice(1)),rob(nums.slice(0,nums.length-1)))

};