帮忙么网 > 算法 > 当前页面

动态规划

2025-01-15 NEW个对象

动态规划的思路分析：

1、将大问题拆分为小问题

2、确定大问题与小问题之间关系

记住过往：

这是算法优化方式，减少重复计算。

一般有自底向上的动态规划、自顶向下的备忘录法

动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如这里的统计方案数的问题，它们都存在一定的递推性质。

前者的递推性质还有一个名字，叫做「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数。

所以在遇到求方案数的问题时，我们可以往动态规划的方向考虑。

相关文章