LeetCode—剑指 Offer 10 - I、II 斐波那契数列、青蛙跳台阶问题 63. 股票的最大利润

剑指 Offer 10 - I、II 斐波那契数列、青蛙跳台阶问题 63. 股票的最大利润

题目描述：
[I] 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
[II] 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
[63] 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

考察重点：三道题目均考察简单的动态规划。第二题虽然题目描述复杂，青但是蛙跳台阶，只可能是从n-1阶跳一次或n-2阶跳两次。即f(n)=f(n-1)+f(n-2），即依然是斐波那契数列问题。

第一题

func fib(n int) int {
    if n == 0{
        return 0
    }
    mod := 1000000007
    a, b, c := 0, 1, 1
    for i := 2;i <= n;i ++{
        c = (a+b)%mod
        a = b
        b = c
    }
    return c
}

第二题

func numWays(n int) int {
	if n == 0 {
		return 1
	}
	a, b, c := 0, 1, 1
	for n > 1 {
		a = b
		b = c
		c = (a + b) % 1000000007
		n--
	}
	return c
}

第三题

func maxProfit(prices []int) int {
    maxPrice := 0
    for i := 1;i < len(prices);i ++{
        nowPrice := prices[i] - prices[i - 1]
        maxPrice = max(maxPrice, nowPrice)
        if prices[i] > prices[i - 1]{
            prices[i] = prices[i-1]
        }
    }
    return maxPrice
}

func max(a, b int)int{
    if a > b{
        return a
    }
    return b
}