计数DP

定义

计数DP（Counting Dynamic Programming）是一种动态规划方法，主要用于解决计数和求和问题。它不同于传统的动态规划，后者通常用于解决最优化问题。

计数DP通过**记忆化搜索**的方法来计算满足特定条件的**解的数量**，常用于求解集合的大小、组合数量等问题。在计数DP中，我们关注的是解的数量而不是解的质量，因此它的应用场景和传统动态规划有所不同。