数位DP，统计1-N中含有“49”的总数

题目：参考数位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 这样的形式。这种形式降低了解题的复杂度，针对这种变形的题目，我们可以有如下思路。

1. 形如X49Y，其中X代表高位的序列，Y代表低位的序列，我们可以先求得Y序列中不包含49的全部序列的数的总和A(Y)，然后计算序列X的序列的数的总和B(X)，使用A(Y)乘上B(X)就是此时49所处的位置的所有可能取值的数的总和。
2. 从低位开始计算每一位49的总和，然后全部相加就是所求的1-N中含有49的总数。
3. 针对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计算求得。