动态规划—剑指10、63

class Solution:
    def fib(self, n: int) -> int:
        a = [0,1]
        for _ in range(n-1):
            nexts = a[-1] + a[-2]
            a.append(nexts)
        return a[n] % 1000000007

class Solution: #a代表当前，b代表下一个
    def fib(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a % 1000000007

第n级可由n-1跳一步或者n-2跳两步

class Solution:
    def numWays(self, n: int) -> int:
        a = [1, 1, 2] # 0阶、1阶、2阶
        for _ in range(n-2):
            nexts = a[-1] + a[-2]
            a.append(nexts)
        return a[n] % 1000000007

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

我没有使用动态规划——使用状态转移方程。
因为我一开始觉得这题像一个列表求连续最大值问题，那么我把每两天的差值计算出来。如第二天-第一天，第三天-第二天…
然后再求连续最大值问题。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dis = []
        for i in range(len(prices)-1):
            gain = prices[i+1] - prices[i]
            dis.append(gain)
        sum = 0
        best = 0
        for x in dis:
            sum += x
            if best 
动态规划：这里是一维数组
 
 
 
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cost, profit = float("+inf"), 0
        for price in prices:
            cost = min(cost, price)
            profit = max(profit, price - cost)
        return profit