c++ - 动态编程: Counting numbers in between

给定两个数字X和Y，它们之间包含多少个数字(至少包括一半的数字)相同？例如，1122和4444将起作用，而11234和112233将不起作用。

显然，最直接的方法是从X开始，一直到Y递增1，然后检查每个数字，但这太慢了，因为X和Y的边界在100和10^18之间。我知道这是动态编程的某种形式，我应该使用字符串来表示数字，但是我无法走得更远。

任何帮助都会被接受。谢谢!

最佳答案

我将通过一些步骤向您解释:

第一步:

为了解决X和Y之间的这种范围问题，请始终通过在0 to X和0 to Y-1之间计数，然后减去结果，使其变得简单。也就是说，如果您有一个像f(N)这样的函数来计算至少有一半数字在0和N之间相同的数字，那么您的最终结果是:

f(X) - f(Y-1)

第二步:

接下来，我们必须计算f(N)。我们将此函数分为2个子函数，一个用于计算数字与N相同的数字的结果(称为f_equal)，另一个用于计算数字小于N的合格数字(称为f_less)。 。例如。如果N为19354，我们计算介于0到9999之间的合格数字，然后用另一种方法计算介于10000到19354之间的喜欢的数字，然后对结果求和。接下来，我将向您解释如何实现这两种方法。

第三步:

在这里，我们要计算f_less方法。您可以通过一些数学来做到这一点，但是我总是喜欢编写一个简单的DP来解决这些任务。我将编写递归函数，无论您可以使用备忘录还是可以使它自底向上并带有一些循环(我都会将其作为练习留给您使用)。

long long f_less(int curDigit, int favNum, int favNumCountSoFar, int nonFavNum, int nonFavNumCountSoFar, int maxDigit){
    if(curDigit == maxDigit ){
        //for numbers with even maxDigit there may be a case when we have 2 favorite numbers
        //and we should count them only once. like 522552
        if(favNumCountSoFar*2 == maxDigit && favNumCountSoFar == nonFavNumCountSoFar) return 1;
        if(2*favNumCountSoFar >= maxDigit) return 2;
        return 0;
    }
    long long res = 0;
    for(int i=(curDigit==0?1:0);i<=9;++i) //skip the leading zero
        if(i==favNum)
            res += f_less(curDigit+1, favNum, favNumCountSoFar + 1, nonFavNum, nonFavNumCountSoFar,maxDigit);
        else
            res += f_less(curDigit+1, favNum, favNumCountSoFar, i, (i==nonFavNum?nonFavNumCountSoFar+1:1),maxDigit);
    return res;
}

并针对0到9之间的所有数字进行调用:

long long res = 0;
for(int maxDigit = 1; maxDigit < NUMBER_OF_DIGITS(N); ++maxDigit)
    for(int favNumber = 0; favNumber < 10; ++favNumber)
        res += f_less(0, favNumber, 0, -1, 0, maxDigit);

第四步:

最后，我们必须计算f_equal。在这里，我们必须将数字保留在字符串中，以始终检查递归函数中的值是否仍在N之下。这是f_equal的实现(再次使用备注或使其自下而上):

string s = NUM_TO_STRING(N);
int maxDigit = s.size();
long long f_equal(int curDigit, int favNum, int favNumCountSoFar,int nonFavNum, int nonFavNumCountSoFar, bool isEqual){ //isEqual checks that whether our number is equal to N or it's lesser than it
    if(curDigit == maxDigit ){
        //for numbers with even maxDigit there may be a case when we have 2 favorite numbers
        //and we should count them only once. like 522552
        if(favNumCountSoFar*2 == maxDigit && favNumCountSoFar == nonFavNumCountSoFar) return 1;
        if(2*favNumCountSoFar >= maxDigit) return 2;
        return 0;
    }
    long long res = 0;
    for(int i=(curDigit==0?1:0);i<=9;++i){ //skip the leading zero
        if(isEqual && i>(s[curDigit]-'0')) break;
        if(i==favNum)
            res += f_equal(curDigit+1, favNum, favNumCountSoFar + 1, nonFavNum, nonFavNumCountSoFar, isEqual && (i==(s[curDigit]-'0')));
        else
            res += f_equal(curDigit+1, favNum, favNumCountSoFar, i, (i==nonFavNum?nonFavNumCountSoFar+1:1), isEqual && (i==(s[curDigit]-'0')));
    }
    return res;
}

并称之为:

long long res = 0;
for(int favNumber = 0; favNumber < 10; ++favNumber)
    res += f_equal(0, favNumber,0, -1, 0, true);

最终结果是res/2。该代码已经过测试并且运行良好。