动态规划的算法作业2020年12月18日_最优子结构性质例子

问题一：请举一个具有最优子结构性质的例子：

例如，迷宫问题：给定一个4*4的迷宫，
1 2 4 5
4 5 7 6
4 6 2 3
3 4 2 1
要求找到从（0，0）到（3，3）的一条权值最短的路径，每次操作只能向右，或者向下移动，这个问题具有最优子结构性质。

分析：
该迷宫可以划分为7层：

到达每一层的一个节点的权值由上一层的两个节点决定

例如：
图中（1，1）节点，节点值为5，想要到达该结点，路径权值由通过点（1，0）或者（0，1）的两条路径的权值大小决定。
这样就可以得到从（0，0）到（3，3）的递归式为：
V（3，3） = min （ V（3，2），V（2，3） ）；

由此可以看出，想要获得到达（3，3）的最小权值路径，问题可以变为到达（3，2）或者到达（2，3）的最小权值路径，由此可以看出，该问题的最优解可以由它的子问题的最优解推导的出，因此说明它具有最优子结构性质。

问题二：请举一个最优子结构的反例：

反例：图中有4个点，如下图所示：

要求从A走到D的所有路径中，总权值除以4得到最小的路径为最优路径：

分析：

从A走到B再走到C，如果根据子结构来看的化，选取4号与2号路径得到8，除以4余数为0，应该是最优解的一部分，然而根据全局来看，最优解为4号与5号与6号，或者1号与5号与3号，并不包含4号与2号这条路径，因此子问题最优无法得到全局最优，因此不满足最优子结构。

问题三：谈谈你对动态规划的理解与心得：

动态规划法，是解决许多实际问题的重要方法，是一种从上往下分析，再从下往上求解的重要方法，它要求待求的问题有：
1、最优子结构性质；
2、无后效性；
3、重复子问题性。
大问题分解为若干个性质相同的子问题求解可以加快整个问题的求解速度，优点是能解决回溯法无法解决的大规模问题。在所有的子问题解决后，这些局部最优解可以拼凑出问题的最优解。
动态规划算法是一个重要的算法，需要我认真理解与掌握，这对我以后的学习十分重要。

人生第一篇博客诞生啦