题目：参考数位DP，统计1-N中含有“49”的总数 另一篇参考文章HDU 3555 Bomb(1-n含有“49”的数字个数)
补充于2017-1-17
我一直在考虑如何思考这种类型的问题，后来从离散数学中找到了一个思路，就是对于计算的计数，如果有可能我们希望能找到一组递推公式，然后按照递推公式进行计算，动态规划其实就是这个思路，可能我理解还是不够深刻！
针对这题我们可以定义一组递推公式。
S0: 代表所有的可能的组合数
S1: 代表所有的不含有49的组合数
S2: 代表所有的含有49的组合数
一般情况：
S0(n) = 10 ^ n;
S1(n) = S0(n) - S2(n);
S2(n) = S2(n-1) * 10 + S1(n-2);
对于整数n的最高位的情况有：
当最高的两位的整数值大于等于49的时候有：
S2(n) = S2(n-1) * 最高位的整数值 + S1(n-2)
否则有：
S2(n) = S2(n-1) * 最高位的整数值
上述的计数方法比下面讲解的思路方法要好点，就是我们找到一个公共的方法用来解决类似的问题。这里先给个代码：
#include <vector>
#include <iostream>
using namespace std;
long long Calculate(unsigned int n)
{
vector<int> vecNum;
for (int i = n; i > 0; i /= 10) {
vecNum.push_back(i % 10);
}
int nl = vecNum.size();
if (nl <= 1) return 0;
vector<vector<long long> > vecMatrix(nl+1, vector<long long>(2, 0));
vecMatrix[0][0] = 1;
vecMatrix[0][1] = 0;
vecMatrix[1][0] = 10;
vecMatrix[1][1] = 0;
// normal
for (int i = 2; i < nl; ++i) {
vecMatrix[i][1] = vecMatrix[i - 1][1] * 10 + vecMatrix[i - 2][0];
vecMatrix[i][0] = (long long)(pow(10, i)) - vecMatrix[i][1];
}
if (vecNum[nl-1] < 4 || (vecNum[nl-1] == 4 && vecNum[nl-2] < 9)) {
return vecMatrix[nl-1][1] * (vecNum[nl-1]+1);
} else {
return vecMatrix[nl-1][1] * (vecNum[nl-1]+1) + vecMatrix[nl-2][0];
}
}
int main(int argc, char ** argv)
{
int n = 9999;
cout << Calculate(n) << endl;
return 0;
}
思路：上述的链接其实已经给了一个算法的思路，但是个人觉得这个算法的思路并不是很好，第一，这个算法思路是个野路子，你得能想到这个DP方程，你才有可能继续进行下去，第二，这个里面涉及到了状态转化，代码中的状态转化也不是很容易理解。
所以，个人总结了另一套不同的算法这个算法采用了类似容斥原理的方式。
我们使用一般性的例子，比如n只能形如9， 99， 999， 9999 这样的形式。这种形式降低了解题的复杂度，针对这种变形的题目，我们可以有如下思路。
- 形如X49Y，其中X代表高位的序列，Y代表低位的序列，我们可以先求得Y序列中不包含49的全部序列的数的总和A(Y)，然后计算序列X的序列的数的总和B(X)，使用A(Y)乘上B(X)就是此时49所处的位置的所有可能取值的数的总和。
- 从低位开始计算每一位49的总和，然后全部相加就是所求的1-N中含有49的总数。
- 针对A(Y) 我们可以建立一张DP状态方程解的表。提高运行的效率。
针对上述的算法，我们仅仅需要考虑如何计算高位的B(X)的可能次数，我们使用GetHighCount函数的方法达到我们的要求。这样我们的算法就能适应输入N的要求。
另外还有个细节，需要特殊考虑最高位。
代码如下：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long GetHighCountForLow(int nBegin, int nEnd)
{
return (long long)pow(10, nEnd - nBegin);
}
long long GetLowCount(const vector<int> & vecN, int nBegin, int nEnd, vector<long long> & dp);
long long CalCountInclude49ForLow(const vector<int> & vecN, int nBegin, int nIndex, int nEnd, vector<long long> & dp)
{
long long X = GetHighCountForLow(nBegin, nIndex);
long long Y = GetLowCount(vecN, nIndex+2, nEnd, dp);
return X * Y;
}
long long GetHighCount(const vector<int> & vecN, int nBegin, int nEnd)
{
long long sum = 0L;
for (int i=nBegin; i<nEnd; ++i) {
sum *= 10L;
sum += vecN[i];
}
if (vecN[nEnd] >= 4)
sum += 1L;
return sum;
}
long long GetLowCount(const vector<int> & vecN, int nBegin, int nEnd, vector<long long> & dp)
{
if (nBegin == nEnd) return 1;
if (nBegin > nEnd) return 0;
if (dp[nBegin] > -1)
return (long long)pow(10, nEnd-nBegin) - dp[nBegin];
long long sum = 0L;
for (int i=nBegin; i<nEnd; ++i) {
sum += CalCountInclude49ForLow(vecN, nBegin, i, nEnd, dp);
}
dp[nBegin] = sum;
return (long long)pow(10, nEnd-nBegin) - dp[nBegin];
}
long long CalCountInclude49(const vector<int> & vecN, int nBegin, int nIndex, int nEnd, vector<long long> & dp)
{
long long X = GetHighCount(vecN, nBegin, nIndex);
long long Y = GetLowCount(vecN, nIndex+2, nEnd, dp);
return X * Y;
}
long long CalCountInclude49(long long n)
{
vector<int> vecN;
for (long long i=n; i>0; i/=10) {
vecN.push_back(i % 10);
}
reverse(vecN.begin(), vecN.end());
if (vecN.size() <= 1) return 0;
if (vecN.size() <= 2) {
if (vecN[0] > 5
|| (vecN[0]==4 && vecN[1] ==9))
return 1;
else
return 0;
}
vector<long long> dp(vecN.size(), -1);
long long sum = 0L;
for (int i=1; i<vecN.size(); ++i)
sum += CalCountInclude49(vecN, 0, i, vecN.size(), dp);
if (vecN[0] > 5
|| (vecN[0]==4 && vecN[1] ==9)) {
sum += CalCountInclude49(vecN, 0, 0, vecN.size(), dp);
}
return sum;
}
int main(int argc, char ** argv)
{
long long n;
cin >> n;
cout << CalCountInclude49(n) << endl;
return 0;
}
我这篇文章的之所以我认为是简单的，因为我的思路相比较参考的文章，我的维度比他的低，我就用了一个一维的数组进行DP。更重要的是，如果你多次测试你会发现DP数组是一个固定的序列，这个序列就是数位（整数的位数）数含有49的个数。我们可以事先生成这张表，而不用每次进行DP计算求得。
