目录
leetcode-动态规划题目方法
五部曲：
1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组
什么是动态规划
动态规划，英⽂：Dynamic Programming，简称DP，如果某⼀问题有很多重叠⼦问题，使⽤动态规划是最有效的。
leetcode-动态规划题目
1.斐波拉切数列
斐波拉切数列：1 1 2 3 5 8
斐波那契数，通常⽤ F(n) 表⽰，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后⾯的每⼀项数字都是前⾯两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你n ，请计算 F(n) 。
⽰例 1：
输⼊：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
⽰例 2：
输⼊：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
答案解析：
/*
数组解决:
时间复杂度：O(n)
空间复杂度：O(n)
*/
func demo1(n int) int {
li := []int{1, 1}
for i := 2; i <= n; i++ {
num := li[i-1] + li[i-2]
li = append(li, num)
}
return li[len(li)-1]
}
当然可以发现，我们只需要维护两个数值就可以了，不需要记录整个序列。demo2
/*
变量解决:
时间复杂度：O(n)
空间复杂度：O(1)
*/
func demo2(n int) int {
num := 1
num2 := 0
if n == 0 {
return num
}
for i := 0; i <= n; i++ {
num, num2 = num2, num+num2
}
return num2
}
/*
递归解决：
时间复杂度：O(2^n)
空间复杂度：O(n)，
*/
func demo3(n int) int {
if n <= 2 {
return n
}
return demo3(n-1) + demo3(n-2)
}
2.爬楼梯
题目：爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
答案：
/*
解析：
利用dp数组方法：
f(x)=f(x-1)+f(x-2)
时间复杂度：$O(n)
空间复杂度：$O(n)
*/
func climbStairs(n int) int {
if n <= 1 {
return n
}
dp := []int{0, 1, 2}
for i := 3; i <= n; i++ {
num := dp[i-1] + dp[i-2]
dp = append(dp, num)
}
return dp[len(dp)-1]
}
/*
变量解决：优化空间复杂度
不用维护数组，维护需要的两个变量
时间复杂度：$O(n)
空间复杂度：$O(1)
*/
func climbStairs2(n int) int {
if n <= 1 {
return n
}
dp1 := 1
dp2 := 2
for i := 3; i <= n; i++ {
dp1, dp2 = dp2, dp1+dp2
}
return dp2
}
3.买卖股票最佳时机(一次买卖)
题目：买卖股票最佳时机，只有一次买卖机会
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
答案：
func main() {
li := []int{7, 1, 5, 3, 6, 4}
fmt.Println(maxProfit(li))
}
/*
解析：
时间复杂度：O(n)
空间复杂度：O(1)
*/
func maxProfit(prices []int) int {
maxNum := 10000000 //7，1，1，
minNum := 0 //0，0，4，
for i := 0; i < len(prices); i++ {
maxNum = min(maxNum, prices[i])
minNum = max(minNum, prices[i]-maxNum)
}
return minNum
}
func min(x, y int) int {
if x > y {
return y
}
return x
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
4.买卖股票最佳时机2(多次买卖)
题目：
描述：给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。返回 你能获得的 最大利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
答案：
/*
低买高买股票，最大收益
思路：
买入：1.当前的价格与明天价格比较，当天低比明天低就买入(如果手里没有股票)，
卖出：1.当天比明天高就当天卖出(如果手里有股票)
2.如果当天价格比明天低，且明天为最后一天，则明天(最后一天)卖出
[]
*/
func maxProfit1(prices []int) int {
is := false
buy := 0 //买入价格
sell := 0 //卖出价格
profit := 0 //总收益
for i := 0; i < len(prices); i++ {
if i == len(prices)-1 && is == true {
//最后一天卖出
sell = prices[i]
profit += sell - buy
break
}
if i == len(prices)-1 {
break
}
if !is {
//手上没有股票，准备买入
if prices[i] <= prices[i+1] {
//当天买入
is = true //已经买入
buy = prices[i] //记录买入价格
continue
}
} else {
//手上有股票，准备卖出
if prices[i] > prices[i+1] {
//当天卖出
is = false //已经卖出
sell = prices[i] //记录卖出价格
profit += sell - buy
}
}
}
return profit
}