【进阶篇 - Day 37】 2020-12-07 -动态规划系列（07. 高频面试题 ）
题目描述
入选理由
- 面试考察的重点题型
题目描述
70. 爬楼梯 > 62. 不同路径 > 121. 买卖股票的最佳时机 > 122. 买卖股票的最佳时机 II > 123. 买卖股票的最佳时机 III > 188. 买卖股票的最佳时机 IV > 309. 最佳买卖股票时机含冷冻期 > 714. 买卖股票的最佳时机含手续费
注意事项
高频系列的题目不要求大家全部做完，做你自己觉得有代表性的题目就好，毕竟不是人人都是西法，可以一秒 5 连鞭
如果碰到不会的题型，比如动态规划，后面会有专题进行讲解的，可以先标记一下，后面学了专题再回来解题
我的回答
https://github.com/leetcode-pp/91alg-2/issues/63#issuecomment-741547306
// TODO: 动态规划
爬楼梯
时空复杂度
时间复杂度：O(n)
空间复杂度: O(n)
var climbStairs = function (n) {
let ans = 0
let dp = [1, 1]
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n]
};不同路径
时间复杂度：O(n*m)
空间复杂度: O(n*m)
路径数 等于 能到左边的路径数加能到上边的路径数
var uniquePaths = function (m, n) {
let dp = Array(m + 1).fill(Array(n + 1).fill(0))
dp[1][1] = 1
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
}
}
return dp[m][n]
};买卖股票的最佳时机 ①
时间复杂度：O(n)
空间复杂度: O(1)
找到最低点，不断的用当前点和最低点比较，就能获得最大收益
var maxProfit = function (prices) {
let max = 0
let min = Infinity
for (let i = 0; i < prices.length; i++) {
min = Math.min(prices[i], min)
max = Math.max(prices[i] - min, max)
}
return max
};