m == 0 일때, 현재 깊이 d에서는 이전 곡의 구성이 어찌됐든 간에, 현재~끝에 나와야할 곡의 구성의 수는 같다.
하지만 m이 0이 아니고, 모든 곡이 나와야한다는 조건이 있으므로, 이전곡의 구성에 영향을 받는데, 이때 이전에 들어간 개별적인 곡의 수가 몇개였는지에 대해서만 생각해주면 된다.
ex) n 3, m 1, d == 5 에서 a b a b c, b a b c a 는 같은 상태이다.
따라서 메모이제이션을 위한 배열을 위와같이 만들어주고, 적절한 조건에 따라서 dp를 진행하면 된다.
코드
#include <iostream>#include <cstring>#define DIV 1000000007using namespace std;int n, m, p, state[101];long long save[101][101];int dp(int d, int count);int main() { memset(save, -1, sizeof(save)); memset(state, -1, sizeof(state)); cin >> n >> m >> p; cout << dp(0, 0);}int dp(int d, int count) { if (p - d < n - count) return 0; if (d == p) return 1; if (save[count][d] != -1) return save[count][d]; long long ans = 0; for (int i = 0; i < n; i++) { if (state[i] == -1 || d - state[i] > m) { int temp = state[i], nc = count; if (temp == -1) nc++; state[i] = d; ans = (ans + dp(d + 1, nc)) % DIV; state[i] = temp; } } return save[count][d] = ans % DIV;}