暴力递归过程的缺陷和解决办法介绍

暴力递归过程的缺陷

在分治阶段，随着递归调用深度的增加，同样问题规模的处理过程在不同的调用深度被重复执行，这是一种性能浪费，对应的解决办法就是记忆化搜索

解决办法:记忆化搜索

所有调用深度共享一个记忆化搜索缓存表，所有子问题的求解过程先去记忆化搜索缓存表里面看看是否有已经处理过的结果，优先获取记忆化搜索缓存表里的处理结果进行返回，避免无效的递归调用，同时对于实际产生了递归调用过程的子问题求解过程，在最终结果值返回之前还需要在记忆化搜索缓存表里面缓存子问题求解得出的答案，供后续优先记忆化搜索缓存值使用

特定记忆化搜索过程的优化

关键点和核心支撑点

狭义关键点描述：所有子问题的记忆化搜索缓存值都可以依赖更小规模子问题的记忆化搜索缓存值来构建

广义关键点描述（待验证，但是有启发作用）：所有子问题的记忆化搜索缓存值都可以依赖其余子问题的记忆化搜索缓存值来构建

核心支撑点：最小规模子问题的记忆化搜索缓存值可以直接枚举构建，作为构建其余记忆化搜索缓存值的基础元信息

递归调用中，所有子问题的记忆化搜索缓存建立过程都可以完全依赖更小规模的子问题的记忆化搜索缓存值，那完全可以将记忆化搜索缓存表的建立过程直接独立出来，因为在所有的递归套路中，问题规模缩小到一定程度后都可以直接得到对应小规模问题最终要返回的结果值，所以所有最小规模问题的记忆化搜索缓存值可以枚举建立，然后依托于所有最小规模问题记忆化搜索缓存值的存在构建所有更大规模问题的记忆化搜索缓存值，反复基于所有现有的记忆化搜索缓存值构建所有稍大规模问题的记忆化搜索缓存值，直到直接得到目标规模子问题的解，直接返回目标子问题的处理结果，省去递归过程的调用

基于特定记忆化搜索过程的优化流程直达动态规划

额外关键点

影响子问题的记忆化搜索缓存值的参数是有限的几个参数，同时这些参数的取值有一定的范围限制

使用动态规划解题的流程

直接根据影响子问题记忆化搜索缓存值的参数的个数以及每个参数的取值范围建立一个多维数组

枚举所有最小规模子问题的解，并在多维数组中找到对应存储最小规模子问题的解的数组元素将结果存入其中

根据子问题记忆化搜索缓存值与其余子问题记忆化搜索缓存值的递推关系，逐个填充多维数组的数组元素，直到目标子问题对应的多维数组的数组元素被填充完成时，可以直接返回结果信息或继续填充数组元素信息

动态规划总结

先是在递归过程中基于记忆化搜索避免重复解相同的子问题，然后发现子问题的描述可以结构化即固定参数个数和每个参数的取值范围，而且子问题的解与其余子问题的解存在递推关系，这一客观规律的发现使得原本需要靠递归调用解决的问题直接转换为结构化数据表的依次填充问题，所以动态规划只是递归调用解决问题的一种等价解决问题方式，由递归调用过程演变而来却又更具高性能特性，时间复杂度更优秀，只有最终数组元素个数有关，但是仅从动态规划过程已经很难看到原本业务逻辑的影子，核心还是递归调用套路，使用动态规划，首先得写出递归调用过程，然后分析发现规律，再使用动态规划解题