数位dp前置技能：记忆化搜索+动态规划 数位dp一般应用于：求出给定区间[A, B]内，符合条件P(x)的数x的个数。条件P(x)一般于数的大小无关，而与数的组成有关。 例题：求区间[a, b]中不包含49的数的个数,其中0<=a, b<=2e9。 我们要求区间[a, b]中不包含49的数的个数，注意到a, b的范围太大，暴力求解是肯定会超时的，因此要考虑动态规划，而如果直接记录下数字，又无法开出这么大的数组，因此我们引入数位dp。 要求区间[a, b]中不包含49的数的个数，很容易想到用前缀和的思想，即[a, b]=[0, b]-[0, a)，我们先求出给定a, b的每个位置...

记忆化搜索前置技能：搜索+动态规划 在信息学中，有两种非常常见的解决问题的方法——搜索和动态规划。搜索的优点在于容易实现，并且如果解决方案存在一定可以找到，但是缺点是它不能很好地处理重叠子问题。动态规划较好地处理了重叠子问题，但是当问题的拓扑关系比较复杂的时候，动态规划也很无奈。记忆化搜索(Memory Search)正是在这种情况下产生的。 记忆化搜索采用的还是搜索的形式，在求解时按照自顶向下的顺序求解，但是每求解一个状态，就将它的解保存下来，在之后遇到重复的状态时，可以不必重新求解。简单来说，就是我们记录一下遇到的每一个状态的值。 例题1： HDU 1331 Function Run ...