Сколько чисел, составленных из N цифр, имеют сумму S? (динамическое программирование)

Question

Так что я просто не могу понять, как ты это делаешь. Вы вводите как N = 2 и S = ​​3 , что означает, сколько чисел, состоящих из 2 цифр, имеют их сумму = 3? Как 12 => 1 + 2 = 3;для N = 2 и S = ​​3 есть 3 числа: 12,30,21.

Я не очень хорошо знаю динамическое программирование. Как вы должны думать об этом алгоритме и подобных ему?

Answer 1

Просто подумайте о решении проблемы грубой силы / возврата. Как бы вы написали это, какие состояния вам нужны и какие состояния можно отбросить?

Для этой конкретной задачи вы можете вставить цифру в позицию, начиная с самой значимой цифры, и перейти к следующей позиции, отслеживая сумму. После вставки всех цифр, если сумма равна нулю, вы увеличиваете свой ответ на 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 намного быстрее и проще, чем другие решения. Удачного кодирования.