Re: [閒聊] 每日leetcode

[dont (dont)]

650. 2 Keys Keyboard

## 思路

兩層for-loop更新DP
dp[j] = min(dp[j], dp[i] + step)

step = copy&paste次數

## Code

```python
class Solution:
    def minSteps(self, n: int) -> int:
        if n == 1:
            return 0

        dp = list(range(1+n))
        for i in range(2, 1 + n//2):
            step = 1  # copy
            for j in range(i+i, 1+n, i):
                step += 1  # paste
                dp[j] = min(dp[j], dp[i] + step)

        return dp[-1]
```

--
http://i.imgur.com/OLvBn3b.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.35.11.142 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724047030.A.BF4.html
※ 編輯: dont (218.35.11.142 臺灣), 08/19/2024 13:59:13
推 sustainer123: 大師
推 DJYOMIYAHINA: 大濕