通用技巧

首先，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，需要你熟练掌握递归思维，只有列出正确的「状态转移方程」，才能正确地穷举。而且，你需要判断算法问题是否具备「最优子结构」，是否能够通过子问题的最值得到原问题的最值。另外，动态规划问题存在「重叠子问题」，如果暴力穷举的话效率会很低，所以需要你使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

备忘录

func memo(n int) int{
    //备忘录，减少重复计算
    memo := make([]int, N+1)
    dp(memo,n)
}



func dp(memo []int, n int) int {
    if n == 0 || n == 1 {
        return n
    }
    // 已经计算过，不用再计算了
    if memo[n] != 0 {
        return memo[n]
    }
    // 状态转移方程 f(n)=f(n-1)+f(n-2) [n=1||n==0: f(n)=n]
    memo[n] = dp(memo, n-1) + dp(memo, n-2)
    return memo[n]
}