爬樓梯
假設(shè)你正在爬樓梯模庐。需要 n 階你才能到達(dá)樓頂烛愧。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數(shù)怜姿。
示例 1：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂慎冤。
- 1 階 + 1 階 + 1 階
- 1 階 + 2 階
- 2 階 + 1 階
// 動態(tài)規(guī)劃，總結(jié)規(guī)律f(n) = f(n-1)+f(n-2)
// 1,1
// 2,2
// 3,3
// 4,5
// 5,8
var climbStairs = function(n) {
//創(chuàng)建一個數(shù)組沧卢，用于爬樓梯種類數(shù)組的數(shù)值
const dp=[]
//初始化數(shù)組蚁堤，1樓1種方式，2樓兩種方式
dp[1] = 1,dp[2] = 2
for(let i=3;i<=n;i++){
dp[i] = dp[i-1]+dp[i-2]
}
console.log(dp[n])
return dp[n]
};
買賣股票的最佳時機(jī)
給定一個數(shù)組 prices 但狭，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格披诗。
你只能選擇 某一天 買入這只股票，并選擇在 未來的某一個不同的日子 賣出該股票立磁。設(shè)計一個算法來計算你所能獲取的最大利潤呈队。
返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤唱歧，返回 0 宪摧。
示例 1：
輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出颅崩，最大利潤 = 6-1 = 5 几于。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時沿后，你不能在買入前賣出股票沿彭。
var maxProfit = function (prices) {
// 初始化最大收益為0，最低買入價格為第一天股票價格
let max_get = 0,min_price = prices[0]
for(var i=0;i<prices.length;i++){
if(min_price>prices[i]){ //如果當(dāng)前價格比最低價格還低
min_price = prices[i] //更新最低價格
}else{ //如果當(dāng)前利潤比之前利潤高尖滚，則更新利潤
max_get = Math.max((prices[i] - min_price),max_get)
}
}
console.log(max_get)
return max_get
}
最大子序和
給定一個整數(shù)數(shù)組 nums 喉刘，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和熔掺。
示例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大饱搏，為 6 。
1置逻、數(shù)組方式
var maxSubArray = function(nums) {
let res = 0,arr = []
for(let i=0;i<nums.length;i++){
if(res>0){
res+=nums[i]
}else{
res = nums[i]
}
arr.push(res)
}
console.log(Math.max(...arr))
};
2推沸、// 動態(tài)規(guī)劃
var maxSubArray = function(nums) {
let bp = [] //初始化一個新數(shù)組
bp[0] = nums[0] //第一個值存入數(shù)組中
for(let i=1;i<nums.length;i++){
if(bp[i-1]>0){ //如果前一個和大于0，繼續(xù)加
bp[i] = bp[i-1] + nums[i]
}else{//如果前一個和小于零券坞，值重置為當(dāng)前值
bp[i] = nums[i]
}
}
console.log(bp)
console.log(Math.max(...bp))
return Math.max(...bp)
};
打家劫舍
你是一個專業(yè)的小偷鬓催，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金恨锚，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)宇驾，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警猴伶。
給定一個代表每個房屋存放金額的非負(fù)整數(shù)數(shù)組课舍，計算你 不觸動警報裝置的情況下 塌西，一夜之內(nèi)能夠偷竊到的最高金額。
示例 1：
輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) 筝尾，然后偷竊 3 號房屋 (金額 = 3)捡需。
偷竊到的最高金額 = 1 + 3 = 4 。
// 動態(tài)規(guī)劃
var rob = function(nums) {
let pb = []
pb[0] = nums[0]
pb[1] = Math.max(nums[0],nums[1])
pb[2] = Math.max(pb[0]+nums[2],pb[1])
if(nums.length==1) return nums[0]
if(nums.length==2) return pb[1]
for(let i=2;i<nums.length;i++){
pb[i] = pb[i-2]+nums[i]
if(pb[i]<pb[i-1]){
pb[i] = pb[i-1]
}
}
console.log(pb)
console.log(Math.max(...pb))
};
