动态规划算法的核心是记住已经求过的解，求解的方式有两种：①自顶向下的备忘录法 ②自底向上。备忘录法在于：在执行的时候把执行过的子节点保存起来，后面要用到的时候直接查表调用的话可以节约大量的时间。自底向上做法在于：从最小的开始计算上去，即先计算子问题再计算父问题，方便后面的直接调用。

用动态规划求解最优化问题的关键是刻画最优解的结构。

适用场景：

• 最优子结构：如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。
• 重叠子问题：如果递归算法反复求解相同的子问题，就称为具有重叠子问题（overlapping subproblems）性质。

简单例子：斐波拉契数列Fibonacci 数列问题
我自己用Python实现了一下：

"""
---------备忘录的求解办法-----
"""


def FibonacciMain1(n):
    if n <= 0:
        return n
    Memo = [-1] * n
    return fib1(n, Memo)


def fib1(n, Memo):
    if Memo[n - 1] != -1:
        return Memo[n - 1]
    if n <= 2:
        Memo[n - 1] = 1
    else:
        Memo[n - 1] = fib1(n - 1, Memo) + fib1(n - 2, Memo)
    return Memo[n - 1]


# print(FibonacciMain1(6))

"""
--------自底向上的记录方法--------
"""


def fib2(n):
    Memo = [-1] * n
    Memo[0] = 1
    Memo[1] = 1
    for i in range(2, n):
        Memo[i] = Memo[i - 1] + Memo[i - 2]
    return Memo[n - 1]


print(fib2(6))

几个动态规划的问题

最优解结构： 最优解结构：

其他例题
参考：https://blog.csdn.net/qq_32400847/article/details/51148917

• 矩阵连乘、走金字塔、最大字段和（https://blog.csdn.net/weixin_37605770/article/details/69371636
  ）
• 最长公共子序列：https://blog.csdn.net/hrn1216/article/details/51534607
• 写一个程序，求出将给定字符串变成回文词所需插入的最少字符数：把原串翻转，再求原串和翻转后串的最长公共子序列，即原串中的最长的回文词
• 凸多边形三角剖分：https://www.cnblogs.com/Jason-Damon/p/3298172.html
  权重值是一个矩阵是什么意思？
• 完全背包问题

01背包：

完全背包：

相对于01背包，完全背包一件物品可以挑选任意多件，那在选择物品的时候，在不大于剩余总重量的情况下，可以选择k(k>=0)件该物品，比较其中最大值。由于k>=1的情况下，选择k个物品与选择k-1个物品存在重复计算，所以在不大于剩余总重量的情况下只需要比较比之前多选择1件该物品就够了

• 双调欧几里得旅行商问题：https://blog.csdn.net/yangtzhou/article/details/83450810

---

参考：
https://blog.csdn.net/u013309870/article/details/75193592