我与动态规划-1

2020-07-20

算法类: 动态规划(DP) 回溯矩阵快速幂递归深度广搜索（DFS BFS）贪心剪纸分治记忆化搜索

题目: 完全背包 01背包

动态规划

在这里插入图片描述

1.首先是想出达到结果的上一步，这也就问题可分解成子问题。那么寻找题解的最后一步（即子问题），通过对比子问题与原问题，找到状态，并且根据状态变换的变量个数确定储存状态解的数组（或者其他数据结构）的维度。

举例：

原问题 找到从(0,0)到（n-1,n-1）的路径数量

子问题 找到从(0,0)到（n-2,n-1）路径的数量加上找到从(0,0)到（n-1,n-2）的路径数量

**F(n-1,n-1)表示要求的路径数量*
直接得到了状态如上设F, 而因为有两个量变化，因此设的存储结构维度为二。

如过状态已经找出来的话，转移方程还是很好列的，有些类似于递推公式，和递归的全局遍历性不同（递归有很多重复计算，个人感觉和当时学迪杰斯特拉算法很像）

举例：就像最简单的斐波那契数列的转移方程为:
*F(n)=F(n-1)+F(n-2)

初始条件很好理解，大都是F(0)=0,简单理解能让迭代进行下去的必要条件（子问题变到了最小单位，主观能够得到）
反向：如果没有初始条件，运算无法继续
边界：eg.例如数组溢出，采取得分的操作（特别是最优问题时，将溢出部分幅值为惩罚项极大的）

举例:寻找某最小值

*F(-1)=Inf or 一个很大的数，一般大于正常结果两三个数量级就够了

其实是客观条件决定的

举例：就像最简单的斐波那契数列:
*F(n)=F(n-1)+F(n-2)
因此必须要知道F(n-1),F(n-2)，因此只能从小到大

二维举例：
路径数量：
因为转移方程：F(n-1,n-1)=F(n-2,n-1)+F(n-1,n-2)
因此从左到右，从上到下

(0,0) …………………. (0,n-1)

(n-1,0) …………………. (n-1,n-1)

## **动态规划在用空间换时间，通过求解每个子问题，并记录下来子问题的解，帮助解决更大的问题。最终求解我们需要的问题。

-------------本文结束感谢您的阅读-------------