不懂了,为什么要写记搜,记忆化搜索有什么好的吗?
我代表递推神教,借天旨意,讨伐记搜!
不是说实话,递推又套路又短又快,无论在码量还是思路上都完胜记搜,为啥不写递推啊。搞不懂了。
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )
int dp(int n) {
if (!n) return 1;
memset(f, 0, sizeof f); memset(bits, 0, sizeof bits); cnt = 0;
while (n) bits[ ++ cnt] = n % 10, n /= 10;
rep(i, 0, bits[cnt]) f[cnt][i][i == bits[cnt]] = 1;
dep(i, cnt, 1) rep(j, 0, 9) rep(k, 0, 1) rep(l, j, 9) {
if (k and l > bits[i - 1]) continue;
f[i - 1][l][k & (l == bits[i - 1])] += f[i][j][k];
} int ans = 0;
rep(j, 0, 9) rep(k, 0, 1) ans += f[1][j][k]; return ans;
}