458. Poor Pigs

https://leetcode.com/problems/poor-pigs/

Python

Top Down DP

• 因為餵食後到Pig GG之前不能再喂其他的豬，所以總共可以執行的步數為ToTest/toDie+，加1是因為左右界都需要包含
• 每次餵食的豬隻數量的指數只要能大於buckets代表豬隻數量足夠

from functools import cache


class Solution:
    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
        steps = minutesToTest // minutesToDie + 1

        @cache
        def dp(exp):
            if steps**exp >= buckets:
                return 1

            return 1 + dp(exp+1)

        return dp(1) if buckets > 1 else 0

Loop

• 同上，也可以直接跑迴圈找出第一個大於buckets的指數結果就好

class Solution:
    def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
        steps = minutesToTest // minutesToDie + 1

        pig_count = 0
        while steps ** pig_count < buckets:
            pig_count += 1

        return pig_count