时间戳

首页 > 解决方案 > 选择球涂成红色的方法有多少？

algorithm - 选择球涂成红色的方法有多少？

问题描述

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

问题陈述：

我们有 3 个整数N、K、Q，其中，

N = 最初在袋子中的球数（从 1 到 N 编号，全部为白色），

K = 匝数，

Q = 我们在每回合从袋子中挑选的球数。

我们被要求返回一个大小为 (N + 1) 的数组，其中arr[i] 表示我们可以挑选球的方式的数量，这样在第 K回合结束时，恰好i数量的球应该是红色的。

我们应该采摘球的方式：

在每个回合中，我们必须从袋子中随机挑选出 Q 个球，并将白色的球涂成红色，红色的球保持原样，然后将它们放回袋子中。

这意味着在任何情况下（转），所有 N 个球（编号从 1 到 N）都存在于 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]

解决方案： 我试图将这个问题作为一个组合（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（动态编程）可以以某种方式为我们节省计算时间，但我很难弄清楚这里存在重复的子问题。

标签： algorithmdata-structurescombinationsdynamic-programmingcombinatorics

解决方案

应用记忆。

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

所以你有一个 r，K 的空间。如果你跟踪在运行期间你已经解决了哪些配置，你应该能够获得多项式复杂度并超过时间限制。

另一种思考方式是，中间状态是有多少种方式可以转 K 轮并有 r 个红球。

推荐阅读