C++ || Dynamic Programming || Easy Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\nUpon reviewing the problem seems to be related to determining the minimum number of p
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nUpon reviewing the problem seems to be related to determining the minimum number of pigs needed to find the poisoned bucket within a certain time frame, considering the constraints on the testing time for each pig. The code employs dynamic programming to solve the problem, using a combination of factorials and a 2D vector to keep track of intermediate results.\n\nMy initial thoughts on solving this problem would involve understanding the constraints and requirements thoroughly. This includes analyzing how the testing time for each pig affects the overall strategy, the concept of dynamic programming, and how to leverage it to optimize the solution.\n\nI would also consider the relationship between the number of pigs, the testing time, and the total time available to solve the problem. This understanding is crucial to come up with an efficient algorithm that minimizes the number of pigs required while ensuring the poisoned bucket can be identified within the given time frame.\n\nAdditionally, exploring the problem through a few examples to understand its nuances and intricacies would be a crucial step. This approach can help in devising a comprehensive plan for solving the problem effectively and optimizing the code for efficiency and scalability.\n<!--\n# Approach\n Describe your approach to solving the problem. -->\n\n\n\n\n# Code\n```\nclass Solution {\npublic:\n    int poorPigs(int N, int I, int T) {\n        vector<long long> f(11, 1);\n        for(int i = 1; i <= 10; i++) f[i] = f[i - 1] * i;\n        T = T / I;\n        if(N == 1) return 0LL;\n        vector<vector<int>> dp(11, vector<int> (T + 1));\n        for(int i = 0; i <= 10; i++) dp[i][0] = 1;\n        for(int i = 0; i <= T; i++) dp[0][i] = 1;\n        for(int i = 1; i <= 10; i++){\n            for(int j = 1; j <= T; j++){\n                for(int k = 0; k <= i; k++) dp[i][j] += f[i] / (f[i - k] * f[k]) * dp[i - k][j - 1];\n            }\n            if(dp[i][T] >= N) return i;\n        }\n        return 11LL;\n    }\n};\n```\n\n![e2515d84-99cf-4499-80fb-fe458e1bbae2_1678932606.8004954.png](https://assets.leetcode.com/users/images/9338d297-7ada-4228-8872-ce4aac453454_1698560361.711557.png)\n
['Math', 'Dynamic Programming', 'Combinatorics', 'C++']