动态规划关键,——,子问题,&,公式化x
来源：证券从业 发布时间：2020-08-28 点击：
动态规划的关键 —— 子问题 & 公式化 • 将问题的规模从 n ⇒ n-1（n/2，或者其他更小的规模）
就将原问题转化为了其子问题； • 公式化：公式化的关键在于对问题进行数学抽象，然后转换为数学语言。
0. 动态规划算法的设计思路 首先设计穷举搜索 • 用制表的方法对穷举搜索（一维表的表长，二维表的 N*N，即包含穷举的含义）进行优化（避免重复计算，可能出现的重复计算项，直接在表中的读取，O(1) 时间）
表可能是一维的（数组），也可能是二维的（二维数组）； – 至于是一维的，还是二维的，依题意（接口而定）而定；
• 斐波那契显然是一维的，而对于像(学期，先修课)，二者之间的关系，则需要用到二维表； 1. 递归式展开 X X + YF • Y ⇒ FX - Y 初始为 FX ，都是字符形式，包括 +/- ，都是有特定含义的字符，如我们要求其展开 n 次后的字符串的长度； x（末尾的 2 表示的是 + 和 F ）
• ylen(n) ⇒ xlen(n-1) + ylen(n-1)+2（末尾的 2 表示的是 - 和 F ）
因此 xlen(n)
其实与 ylen(n)
大小是一致的，进一步可转化为如下递归式：
• len(n) = 2len(n-1) + 2
推荐访问:公式化 关键 规划