Re: [閒聊] 每日leetcode
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
推
08/19 13:58,
1年前
, 1F
08/19 13:58, 1F
推
08/19 14:16,
1年前
, 2F
08/19 14:16, 2F
討論串 (同標題文章)
完整討論串 (本文為第 735 之 1548 篇)：