Динамическое программирование - это популярный метод компьютерного программирования, который фокусируется на решении данной проблемы путем решения ее подзадач с использованием надлежащих базовых условий и запоминания. В Интернете есть различные проблемы с DP. Digit DP - одна из таких техник. В этом решение можно найти, играя с цифрами. Мы рассматриваем числа как строки и добавляем все возможные цифры, которые могут находиться в любой позиции, и таким образом составляем новые числа. Это можно понять с помощью одной такой постановки задачи.

ЗАЯВЛЕНИЕ О ПРОБЛЕМЕ:

Данная постановка задачи взята из SPOJ.

Здесь даны два числа, скажем, a, b. В постановке задачи говорится, что нужно найти сумму цифр чисел между a и b.

Ограничения: 0 ‹= a, b‹ = 10⁹

ПОИСК РЕШЕНИЯ ДЛЯ ДАННОГО ДИАПАЗОНА:

Нам нужно найти сумму цифр чисел между a и b. Это можно еще больше упростить, если мы просто найдем сумму цифр числа от 0 до b и вычтем из нее сумму цифр чисел от 0 до a.

Это можно проиллюстрировать так, как если бы у нас есть некоторая функция, скажем resolve1 (int no), которая возвращает сумму цифр чисел между 0 и данным числом, тогда решение данной задачи может быть показано как: - resolve1 (b) -solve1 (а-1).

СОСТОЯНИЯ ПРОБЛЕМЫ DP И РЕШЕНИЕ:

Digit DP - это метод, в котором мы пытаемся сформировать действительные числа в соответствии с данной постановкой задачи. Теперь предположим, что задан диапазон от 0 до 5445. Таким образом, в соответствии с нашим подходом мы сначала найдем числа, которые находятся между 0 и 5445. Это требует формирования чисел, которые меньше 5445. Теперь предположим, что число, которое было сформировано до позиции 3 544_. Последний пробел можно заполнить цифрами 0,1,2,3,4,5, а не 6,7,8,9, иначе полученное число станет больше заданного числа 5445. Таким образом, одним из важных состояний является pos. - позиция следующей цифры. Как видно из вышеприведенного подхода, важно проверить, находится ли сформированное число в заданном диапазоне или нет. Для этого у нас может быть связанный с ним флаг, например f. Этот флаг поможет нам следующим образом: -

f = 0 означало бы, что есть ограничения на цифру, которую нужно вставить.

f = 1 будет означать, что для следующей позиции может быть выбрана любая цифра.

Последнее состояние, которое нам потребуется сохранить, - это сумма до данной позиции и для данного флага.

Таким образом, основная функция, которая дала бы сумму цифр числа:

int a,b;
long long int DP[12][180][2];
vector<int> num;
long long int solve(int pos,int sum,int f){
if(pos==num.size()){
  return sum;
}
if (DP[pos][sum][f]!=-1) return DP[pos][sum][f];
long long int res=0;
int lmt;
if(f==0){
  lmt=num[pos];
}
else lmt=9;
for(int dgt=0;dgt<=lmt;dgt++){
   int nf=f;
   if(f==0 && dgt<lmt) nf=1;
   res+=solve(pos+1,sum+dgt,nf);
}
return DP[pos][sum][f]=res;
}

В этом DP [pos] [sum] [f] хранится ответ для данной позиции, суммы и состояния. Если DP [pos] [sum] [f] не равно -1, т.е. он сохраняет уже вычисленное значение, тогда он просто возвращает это значение. Затем мы проверили, каково значение нашего флага f. Если значение нашего флага равно 0, мы должны проверить, какая максимальная цифра может быть помещена в эту позицию. Как и в предыдущем примере, мы видели 544_. Здесь можно ввести цифры 0,1,2,3,4,5. Таким образом, предел (здесь имя lmt-переменной) - это цифра, которая присутствует в исходном номере в данной позиции. Если f = 1, мы можем явно выбрать любую цифру от 0 до 9 для данной позиции. Например, число, которое мы сформировали, - 543_. Таким образом, последний пробел может быть заполнен цифрами от 0 до 9. Следующая часть состоит из повторения следующей позиции и суммы и нового флага, который изменяется в соответствии с условием.

Это значение затем сохраняется в DP [pos] [sum] [f].

Другая функция решения1 (int no) может помочь нам найти сумму для разных чисел. Для этого код будет: -

long long int solve1(int no){
 num.clear();
 while(no!=0){
  num.push_back(no%10);
  no/=10;
 }
 memset(DP,-1,sizeof(DP));
 reverse(num.begin(),num.end());
 long long int result=solve(0,0,0);
 return result;
}                          }

Временная сложность описанного выше подхода будет O (10 * pos * sum * f). Здесь pos может принимать значения log (n), sum может принимать значения 10 * log (n), flag может принимать 2 значения. Таким образом, общая временная сложность составляет O ((log (n)) ²).

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

По этой ссылке представлено все решение.