力扣动态规划问题求解思路

定义：
动态规划算法是通过拆分问题、定义问题状态和状态之间的关系，使得问题能够以地推（或者说分治）的方法解决。动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
基本思想与策略编辑
由于动态规划问题解决的问题多数有重叠子问题这个特点，为了减少重读计算，对每一个子问题只求解依稀，将其不同阶段的不同状态保存在一个二维数组中。

首先是拆分问题：
根据问题的可能性将问题划分成一步一步这样就可以通过递推或者递归来实现。动态规划这一类问题就是从后往前推导，有时候很容易就知道：如果只有一种情况时，最佳的选择应该怎么做，然后根据这个最佳选择往前一步进行推导，得到前一步的最佳选择。
然后定义问题状态和状态之间的关系
拆分步骤之间的关系，用一种量化形式表现出来。
定义下面的两段
比如我们找到了最优解，我们应该将最优解保存下来，为了往前推导时能够使用前一步的最优解，在这个过程中难免有一些相比最优解差的解，此时我们应该放弃，只保存最优解，这样我门每一次都把最优解保存下来了，大大降低了时间复杂度。

经典的数字三角形问题(简单易懂,经典动态规划);

可以看出每走第n行第m列时有两种后续:向下或者向右下
由于最后一行可以确定,当做边界条件,所以我们自然而然想到递归求解


其实仔细观察,上面的解答过程时间复杂度难以想象的大,那是因为他对有的数字的解进行了多次的重复计算,具体如下图:

如果不明白上图,可以把每条路径都画出来,观察每个数字有多少条路径经过了他,就会一目了然
然后我们就可以自然而然的想到,如果我们每次都把结果保存下来,复杂度就会大大降低


其实这是动态规划很精髓的一部分,是减少复杂度的主要原因
我们都知道,递归一般情况下是可以转化为递推的,不详细解释了,贴上答案:

其实,仔细观察该解题过程,该过程就是标准的动态规划解题过程,如果把该过程画出来(找到每一步的最优解,其他的舍弃)对动态规划会有更深刻的解法
还有就是,递推的另一个好处是可以进行空间优化,如图:

递归到动态规划的转化方法为：
如果该递归函数有n个参数，纳闷就定义一个n维数组，数组下边是递归函数的取值范围（也就是数组没一维的大小），数组元素的值就是递归函数的返回值（初始化为一个标志值，表明还未被填充），这样就可以从边界值开始逐步的填充数组，相当于计算递归函数的逆过程。
动规解题的一般思路(标准官方,不过经过前边讲解应该就能理解了):

1、将原问题分解为子问题(开头已经介绍了怎么分解) (注意:1,子问题与原问题形式相同或类似,只是问题规模变小了,从而变简单了; 2,子问题一旦求出就要保存下来,保证每个子问题只求解一遍)
2、确定状态(状态:在动规解题中,我们将和子问题相关的各个变量的一组取值,称之为一个"状态",一个状态对应一个或多个子问题所谓的在某个状态的值,这个就是状态所对应的子问题的解,所有状态的集合称为"状态空间".我的理解就是状态就是某个问题某组变量,状态空间就是该问题的所有组变量) 另外:整个问题的时间复杂度就是状态数目乘以每个状态所需要的时间
3、确定一些初始状态(边界条件)的值 (这个视情况而定,千万别以为就是最简单的那个子问题解,上面只是例子,真正实践动规千变万化)
4、确定状态转移方程 (这一步和第三步是最关键的 记住"人人为我"递推,由已知推未知)
适合使用动规求解的问题:
1,问题具有最优子结构
2,无后效性 说的花里胡哨的,其实一般遇到求最优解问题一般适合使用动态规划