专题：动态规划

简介

动态规划问题的难点在于对问题进行合理划分，将大问题转变为小问题的组合，形成递推关系，通过归纳法将问题得到解决；

动态规划最关键的地方在于对问题进行正确的抽象和建模，进而建立递推公式；

步骤

• 函数定义：定义问题目标函数，目标函数可通过子目标函数组合而成，子函数需要包含目标函数的所有情形且不能重叠；
• 递推公式：定义最终函数 和 子目标函数之间的递推关系，通过将目标问题分解为规模更小的子问题组合来递推解决目标问题；
• 初始条件：
• 终止条件:

相关题目