Dynamic Programming
Idea\nlet\'s try to compute the maximum number of buckets we can check with n pigs and T trials (trials is the maximum number of tests in the given time)\nFor e
# Idea\nlet\'s try to compute the maximum number of buckets we can check with $$n$$ pigs and $$T$$ trials (trials is the maximum number of tests in the given time)\nFor each bucket we\'ll feed with a different combination of pigs, so that if a specific combination of pigs die, we can exactly obtain the bucket. The number of combinations we can obtain from $$n$$ pigs is $$2 ^ n$$. In worst case $$(buckets = 1000$$ $$and$$ $$trials = 1)$$ we only require $$log_2(1000) = 10$$ pigs. \n\nAssume we have more than one trials. In this case we can use a certain combination many times on different buckets, and if that combination of pigs die we can eliminate other buckets and check only these buckets with remaining number of pigs. for ex- if we have $$10$$ pigs and we tested a combination $$(1, 2, 4, 5, 7, 9)$$ on $$100$$ buckets, and this combination of pigs die, we can be sure that poisoned bucket is in these $$100$$ buckets and we can test these $$100$$ buckets again with remaining pigs $$(3, 6, 8, 10)$$\n\nIntuition behind dynamic programming approach:\n$$dp[i][j] =$$ number of buckets can be tested using $$i$$ pigs and $$j$$ trials\n\nto obtain $$dp[i][j]$$ we\'ll make $$2 ^ i$$ combinations, for each combination we need know on how many buckets we can place that combination, to know that we must check the maximum number of buckets that can be checked in $$j - 1$$ trials from the remaining pigs\n\n$$dp[i][j] = \\sum_{k=0}^i iC_k * dp[i - k][j - 1],$$  $$iC_k =$$ number of ways of selecting $$k$$ pigs from $$i$$ pigs\n\n# Base cases:\nif number of $$buckets = 1$$, we need $$0$$ pigs\nif number of $$pigs = 0$$, we can check only at max $$1$$ bucket\nif number of $$trials = 0$$, we cann check at max $$1$$ bucket\n\n# Time Complexity:\n$$O(10 * (Trials) ^ 2)$$\n\n$$Trials = TotalTime$$ $$/$$ $$TestTime$$\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```
['Dynamic Programming', 'C++']