初级算法 动态规划

爬楼梯

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

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

/**
 * @param {number} n
 * @return {number}
 */
//  f(n) = f(n-1) + f(n-2)
//  f(1) = 1
//  f(2) = 2 
var climbStairs = function(n) {
    let arr = [1,2]
    for(let i = 2; i< n; i++){
        arr[i] = arr[i-1] + arr[i-2]
    }
    return arr[n-1]
};

买卖股票最佳时机

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

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

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

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if (prices == null || prices.length == 0) return 0;
    let min = prices[0]
    let maxPro = 0
    for(let i =0;i<prices.length;i++){
        min = Math.min(min,prices[i])
        maxPro = Math.max(maxPro,prices[i]-min)
    }
    return maxPro
};

最大子序和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

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