Проблема с реализацией рекурсивного решения стандартной задачи на ДП

Информатика
1

Недавно начал решать задачи по ДП. (Dice Combination)
Не могу понять где допустил ошибку в рекурсивной реализаций задачи
Помогите пожалуйста
вот код

#include <bits/stdc++.h>
using namespace std;

int dp[1000007];
bool dp1[1000007];
vector a = {1, 2, 3, 4, 5, 6};
int s = 0;
int solve(int n){
if(n == 0)return 1;
if(n < 0)return 0;
if(dp1[n] == true)return dp[n];

s = 0; 
for(auto x : a){
	s += solve(n - x); 
}
dp[n] = s; 
dp1[n] = true;
return s;

}

int main(){

int n; 
cin >> n; 
cout << solve(n); 

return 0;

}

Вот условие

Your task is to count the number of ways to construct sum n by throwing a dice one or more times. Each throw produces an outcome between 1 and 6.

For example, if n=3, there are 4 ways:

  • 1 + 1 + 1

  • 2 + 1

  • 1 + 2

  • 3

1 лайк
2

по крайней мере посмотри на то, как ты работаешь с переменной s. попробуй распечатай ее на каждом уровне рекурсии с n =2.

5 лайков