有多少种方法可以挑选球来涂成红色？

Question

如何使用DP优化解决方案？

问题陈述:

We are given 3 integers N, K, Q where,

N = number of balls initially in the bag(numbered from 1 to N and all are white-colored),

K = number of turns,

Q = The number of balls we pick at each turn from the bag.

We are asked to return an array of size (N + 1), where arr[i] represents the number of ways we can pick the balls such that at end of Kth turn exactly i number of balls should be red-colored.

我们捡球的方式:

At each turn we have to pick exactly Q balls from the bag randomly, and paint white ones to red, and leave red ones as it is, then replaces them back into the bag.

This means at any instance(turn) all the N balls(numbered from 1 to N) are present in the bag.

限制条件：

 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]

解法： 我试图将此问题作为 combination(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;
  }

With this code, even on input N = 50, Q = 3, K = 6 this is giving TLE(time limit exceeded error)

所以我认为 DP（动态规划）可以以某种方式节省我们的计算时间，但我很难弄清楚这里存在如何重复的子问题。

Answer 1

我们可以考虑一个简单的例子，其中出现重复的子问题。取Q = 2；下面没有显示所有的递归调用，只是足以看出一些是用相同的参数进行的。

假设 w = 4、r = 1 和 K = 3。
- 递归调用 w = 3, r = 2, K = 2 当再有 1 个白球被涂成红色时。
  - 递归调用 w = 1, r = 4, K = 1 当再有 2 个白球被涂成红色时
- 递归调用 w = 2, r = 3, K = 2 当再有 2 个白球被涂成红色时。
  - 递归调用 w = 1、r = 4、K = 1 当再有 1 个白球被涂成红色时

所以，w = 1、r = 4和K = 1的子问题至少被递归算法求解了两次。如果使用记忆化或者动态规划，这个子问题的解只会被计算一次然后重复使用。

Answer 2

应用记忆。

// 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

为此，我们可以忽略运行.

的常量参数

C 和 Q 是常数，所以我们可以忽略它们。
B+r 是常量所以我们可以忽略其中之一（我选择忽略 B）
r+w 是常数，所以我们可以忽略其中之一（我选择忽略 w）。

所以你有 space 的 r，K。如果你跟踪你在运行期间已经解决的配置，你应该能够拥有多项式复杂度并击败时间限制。

换个思路想，中间状态就是有多少种方法可以转K圈，有r个红球。

有多少种方法可以挑选球来涂成红色？

Number of ways to pick the balls to paint in red color?

algorithm

data-structures

combinations

dynamic-programming

combinatorics