c – 动态编程：计算两者之间的数字

第一步：

为了解决X和Y之间的这种范围问题,总是通过在0到X和0到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来解决这些任务.我会编写递归函数,无论你是否可以使用memoization,或者你可以通过一些循环自下而上(我会把它作为一种练习).

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,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,-1,maxDigit);

第四步：

最后我们必须计算f_equal.这里我们必须将数字保存在一个字符串中,以便始终检查我们是否仍然在递归函数中的N以下范围内.这是f_equal的实现(再次使用memoization或自下而上)：

string s = NUM_TO_STRING(N);
int maxDigit = s.size();
long long f_equal(int curDigit,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,isEqual && (i==(s[curDigit]-'0')));
        else
            res += f_equal(curDigit+1,isEqual && (i==(s[curDigit]-'0')));
    } 
    return res;
}

并称之为：

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

最终结果是res / 2.代码经过测试并运行良好.