Как оптимизировать решение с использованием DP?
Постановка задачи :
Нам дано 3 целых числа N, K, Q , где
N = количество шариков, изначально находящихся в сумке (пронумерованных от 1 до N (все они белого цвета),
K = число витков,
Q = Количество шаров, которые мы отбираем на каждом шагу из сумки.
Нас просят вернуть массив размера (N + 1) , где arr [i] представляет количество способов, которыми мы можем подобрать шары, так что в конце Kth поворот точно i количество шаров должно быть красного цвета.
Способ, которым мы должны собирать шары :
В каждый ход мы должны случайным образом выбирать из сумки ровно Q шариков, раскрашивать белые в красные и оставлять красные как есть, а затем заменять их обратно в сумку.
Это означает, что в любой момент (ход) все N шаров (пронумерованных от 1 до N) присутствуют в сумке .
Ограничения:
1<=N<=100
1<=K<=100
1<=Q<=N
Пример :
**INPUT**:
N = 3, K = 2, Q = 2,
Let the balls are numbered as 1, 2 and 3.
All possible ways to pick balls in K = 2 turns:
pick1 pick2
(1,2) (1,2) = 2 red balls
(1,3) (1,3) = 2 red balls
(3,2) (3,2) = 2 red balls
(1,2) (1,3) = 3 red balls
(1,2) (2,3) = 3 red balls
(1,3) (1,2) = 3 red balls
(1,3) (2,3) = 3 red balls
(2,3) (1,3) = 3 red balls
(2,3) (1,2) = 3 red balls
so, we have
0 ways to paint exactly 0 ball red in K number of turns,
0 ways to paint exactly 1 ball red in K number of turns,
3 ways to paint exactly 2 balls red in K number of turns &
6 ways to paint exactly 3 balls in K = 2 number of turns.
**OUTPUT**:
arr[] = [0, 0, 3, 6]
Решение: Я пытался решить эту проблему как комбинация (C (n, r)) проблема. И решил ее рекурсивно следующим образом:
// utility function to calculate C(n,r)
void calculate_CnR(vector<vector<long long> > &C){
for(int n = 0; n < C.size(); n++){
for(int r = 0; r < C[0].size(); r++){
if(n >= r){
if(n == r || r == 0) C[n][r] = 1;
else if(r == 1) C[n][r] = n;
else C[n][r] = (C[n - 1][r - 1] % (1000000007) + C[n - 1][r] % (1000000007)) % (1000000007);
}
}
}
}
// main method
// B = number of balls left to paint red
// r = number of red balls present in bag currently
// w = number of white balls present in bag currently
// K = number of turns left
// Q = number of balls need to pick at each turn
// C = to access C(n,r) value in O(1) time
long long num_ways(int B, int r, int w, int K, const int &Q, const vector<vector<long long> > &C){
// base case
if(K == 0){ //turns over
if(B > 0)
return 0;
else if(B == 0)
return 1;
}
// decide maximum number of white balls we can pick
long long max_ = min(B, Q);
long long ways = 0;
for(int white_picks = 0; white_picks <= max_; white_picks++){
int red_picks = Q - white_picks;
if(red_picks <= r && white_picks <= w){ // red/white_picks num_balls must be present in the bag to pick.
ways += (
((C[w][white_picks] * C[r][red_picks]) % 1000000007)
*
(num_ways(B - white_picks, r + white_picks, w - white_picks, K - 1, Q, C) % 1000000007)
) % (1000000007);
}
}
return ways;
}
int main(){
// C[n][r] represents nCr
vector<vector<long long> > C(101, vector<long long>(101, 0));
calculate_CnR(C);
int tests = (cin>>tests, tests);
while(tests--){
int N = (cin>>N, N); // num balls
int K = (cin>>K, K); // turns
int Q = (cin>>Q, Q); // num of balls picked at each turn
vector<long long> ways(N + 1, 0);
for(int i = 1; i <= N; i++){
ways[i] = num_ways(i, 0, N, K, Q, C) % (1000000000 + 7);
}
}
return 0;
}
С этим кодом даже на входе N = 50, Q = 3, K = 6 это дает TLE (ограничение по времени ошибка превышена)
Так что я думаю, что DP (динамическое программирование c) может сэкономить нам время вычислений, но мне трудно понять , как существуют повторяющиеся подзадачи здесь.