Просто подумайте о решении проблемы грубой силы / возврата. Как бы вы написали это, какие состояния вам нужны и какие состояния можно отбросить?
Для этой конкретной задачи вы можете вставить цифру в позицию, начиная с самой значимой цифры, и перейти к следующей позиции, отслеживая сумму. После вставки всех цифр, если сумма равна нулю, вы увеличиваете свой ответ на 1.
Так что решение Backtrack будет выглядеть примерно так:
void f(int pos,int sum) {
if(pos == n) {
if(!sum) ans += 1;
return;
}
for(int i = 0 ; i < 10 ; i++)
f(pos + 1 , sum - i);
}
Если вы можете придуматьРешение BackTrack тогда уже 90% вашей работы выполнено. Для динамического программирования вам просто нужно сохранить состояния, чтобы вам не пришлось пересчитывать состояние дважды. Кроме того, подумайте о угловых и базовых случаях. В нашем решении backTrack у нас есть ошибка. Мы не должны вставлять 0 в старших разрядах. Исправление всего этого Код должен выглядеть примерно так:
#define maxN 1000
#define maxSum 1000
#define i64 long long int
#define mod 1000000007
int n;
i64 dp[maxN][maxSum];
i64 f(int pos,int sum) {
if(sum < 0) return 0;
if(pos == n)
{
if(!sum) return 1;
return 0;
}
if( dp[pos][sum] != -1)
return dp[pos][sum];
int lo = 0;
if(!pos)
lo = 1;
i64 ans = 0;
for(int i = lo ; i < 10 ; i++)
ans += f(pos + 1, sum - i);
ans %= mod;
return dp[pos][sum] = ans;
}
int main()
{
int s;
cin >> n >> s;
memset(dp,-1,sizeof dp);
cout << f(0,s) << endl;
return 0;
}
Временная сложность кода составляет O(maxN * maxSum * 10)
. Вы можете найти более оптимизированное решение в Интернете. Но как только вы узнаете немного больше о динамическом программировании, вы поймете, что придумать решение dp намного быстрее и проще, чем другие решения. Удачного кодирования.