算法学习小总结

递归到动归的一般转化方法：

​ 递归函数有N个参数，就定义一个N维的数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值，这样就可以从边界值开始，逐步填充数组，相当于计算递归函数的逆过程。

动归解题一般思路：

​ 1：把原问题分解成若干个子问题，子问题和原问题形式相同或类似，只不过规模变小了。子问题都解决，原问题也就解决了。 子问题的解一旦求出就会被保存，所以每个子问题只需求解一次。

​ 2：确定状态 和子问题相关耳朵各个变量的一组取值，称之为一个“状态”。一个状态对应于一个或多个子问题，所谓某个状态下的“值”就是这个状态对应的子问题的解。 所有“状态”的集合，构成问题的“状态空间”。“状态空间”的大小，与动态规划解决问题的时间复杂度直接相关。在数字三角形的例子里，一共花有N* (N+1)/2个数字， 所以就有N*(N+1)/个状态。整个问题的时间复杂度是状态数目乘计算每个状态所需要的时间。

​ 3：确定一些初始状态（边界）的值。

​ 4：确定状态转移方程，即递推公式。

能被用动归解决的问题的特点：

​ 1）问题具有最优子结构性质，如果问题的最优解包含的子问题的解也是最优的，就乘该问题具有最优子结构性质。

​ 2）无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值油管，和之前是采取哪种手段或经过哪条路径演变到当前这若干个状态，没有关系。

递归注意事项：

​ 函数的局部变量存放在栈中，如果有体积大的局部变量，或许可能会导致栈溢出

​ —>可以考虑使用全局数组或动态分配数组

初始化一个大小为n的堆所需要的时间为O（n）

本文地址：https://blog.csdn.net/qq_30204577/article/details/109257172