经典算法之动态规划（golang）

动态规划思想：把一个问题分解成若干个子问题，并找出其最优解决方法

动态规划的解题关键在于：

• 1.根据问题可能性进行拆分。
  从最简单的情况下进行分析，从下往上逐步分析。
• 2.找到状态转移方程式，保存最优解。
  方程式其实就是在满足某个条件下的递推通项公式，同时也要注意条件范围和边界处理。

例题：买卖股票最佳时机

给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。

package main

func maxProfit(prices []int) int {
   n := len(prices)
   dp := make([][2]int, n)
   dp[0][1] = -prices[0]
   for i := 1; i < n; i++ {
      dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
      dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
   }
   return dp[n-1][0]
}

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