数位DP一般有两种思路
正向:利用公式化的DP关系从低位往高位递推
逆向:记忆化搜索
其中需要注意的是:记忆化搜索时的dp更新,往往会一不小心犯错,例如
for (top = 1; top<= nf; ++top)
{
memset(dp, -1, sizeof dp);
res += dfs(0, top, 0, 0, top==nf);
}
如果是按高到低位分别计算,一般需要将dp清空
hdu 4933 Miaomiao's Function
该题考点确实变态,借鉴了别人的思路。
dp[i][2]表示:i当前位数(起始位非0),数的总个数&满足题意(从高到低位,奇数位和减去偶数位和)所有数计算结果的和
因......
阅读全文