动态规划算法的核心是记住已经求过的解，求解的方式有两种：①自顶向下的备忘录法 ②自底向上。备忘录法在于：在执行的时候把执行过的子节点保存起来，后面要用到的时候直接查表调用的话可以节约大量的时间。自底向上做法在于：从最小的开始计算上去，即先计算子问题再计算父问题，方便后面的直接调用。
用动态规划求解最优化问题的关键是刻画最优解的结构。
适用场景：
- 最优子结构：如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。
- 重叠子问题：如果递归算法反复求解相同的子问题，就称为具有重叠子问题（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背包，完全背包一件物品可以挑选任意多件，那在选择物品的时候，在不大于剩余总重量的情况下，可以选择k(k>=0)件该物品，比较其中最大值。由于k>=1的情况下，选择k个物品与选择k-1个物品存在重复计算，所以在不大于剩余总重量的情况下只需要比较比之前多选择1件该物品就够了
参考：
https://blog.csdn.net/u013309870/article/details/75193592
