# 初级算法 动态规划
# 爬楼梯
假设你正在爬楼梯。需要 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);
};