SPOJ Сумма цифр

Question

Я пытаюсь решить проблему http://www.spoj.com/problems/CPCRC1C/ с использованием подхода обсуждается в
http://goo.gl/YzEwXR

Это моя реализация алгоритма выше

void solve(int i, bool lo, bool hi, char *A, char *B, int n, unsigned long long &sum,int numSum) { 

if (i == n) { 
    sum+=numSum; 
    return; 
} 

char d = hi ? '0' : A[i]; 
char end = lo ? '9' : B[i]; 
for (; d <= end; d++) { 

    int nnumSum=numSum ; 
    nnumSum += (d-48); 
    // cout<<"\nd="<<d<<" sum="<<nnumSum; 
    solve(i + 1, lo || d < B[i], hi || d > A[i], A, B, n, sum,nnumSum); 
} 
} 

Можете ли вы предложить мне, как я может оптимизировать алгоритм с помощью memoization?

Большое спасибо за ваше время

Answer 1

CPCRC1C

1) sum of digits from 1 to b, let this count be sum(b) 

2) sum of digits from 1 to a-1, let this count be sum(a-1) 

разница между двумя Вернутся подсчетов

Как вычислить сумму (х)? Давайте попробуем найти образец

Что такое сумма (9)?

1 2 3 4 ........... 9 
9*10/2 = 45 

Что такое сумма (19)? сумма (9) + сумма цифр в следующих числах

10 11 12 13 ....... 19 
10 + 9*10/2 = 10 + 45 [10 is sum of first digit in all numbers] 

Что такое сумма (29)? сумма (19) + сумма цифр в следующих числах

20 21 22 23 ........29 
20 + 9*10/2 = 20 + 45 

Что такое сумма (100)?

45 + (10 + 45) + (20 + 45) + (30 + 45) + ..... (90 + 45) 
45*10 + (10 + 20 + 30 ... 90) 
45*10 + 10(1 + 2 + ... 9) 
45*10 + 45*10 
45*20 

Мы можем использовать выше шаблон, чтобы придумать формулу, которая может непосредственно вычислить сумму

Источник: GeeksforGeeks