題目敘述 Leetcode: 650. 2 Keys Keyboard
一開始初始化的時候，記事本上只有一個字元'A'。
只允許下列兩種操作- 複製目前記事本上的整個字串。
- 貼上之前複製的內容，串接在尾端。
請問，最少需要幾個操作，
才能製造出內容都是 "AAA...A"，長度為n，內部每個字元都是'A'的字串?
測試範例
Example 1:
Input: n = 3
Output: 3
Explanation:
一開始，初始字串是A
第一步，複製整個字串A
第二步，貼上A，內容變成AA
第三步，貼上A，內容變成AAA
任務完成，最少需要三步，來生成長度為3，內部每個字元都是'A'的字串"AAA"
Example 2:
Input: n = 1
Output: 0
一開始，初始字串是A
所需步數為零步。
約束條件
Constraints:
1 <= n <= 1000
n介於1~1000之間。
觀察 試著從小單元複製貼上，精簡步數。
假如n不是質數的時候，
可以試著從更小的小單元(小單元的長度是n的因數)複製貼上，製造出長度為n的字串。
例如: 當n=4時
初始化是A
第一步 複製A
第二步 貼上A，整個字串現在是"AA"
第三步 複製"AA"
第四步 貼上A，整個字串現在是"AAAA"
例如: 當n=6時
初始化是A
第一步，複製A。
第二步，貼上A，整個字串現在是"AA"。
第三步,，貼上A，整個字串現在是"AAA"。
第四步，複製AAA。
第五步，貼上AAA，整個字串現在是"AAAAAA"。
假如n是質數的時候，
代表無法從更小的小單元(小單元的長度是n的因數)複製貼上，製造出長度為n的字串。
只能從A開始一個字元一個字元慢慢貼上。
例如: 當n=3時
初始化是A
第一步，複製A。
第二步，貼上A，整個字串現在是"AA"。
第三步，貼上A，整個字串現在是"AAA"。
例如: 當n=5時
初始化是A
第一步，複製A。
第二步，貼上A，整個字串現在是"AA"。
第三步，貼上A，整個字串現在是"AAA"。
第四步，貼上A，整個字串現在是"AAAA"。
第五步，貼上A，整個字串現在是"AAAAA"。
演算法 字串DP
怎麼定義DP狀態?
定義 DP[ i ] 代表長度為 i 的字串，所需要的最少操作數目。
最後所求就是DP[ n ]
怎麼推導DP狀態轉移關係式?
當 i 不是質數時，
可以化簡到長度為因數的更小字串，依靠複製貼上，來製造長度為 i的字串。
DP[ i ] = min{ DP[ i // j ] + 1次複製 + (j-1)次貼上， 而且i 是 j 的倍數 }
DP[ i ] = min{ DP[ i // j ] + j， 而且 i 是 j 的倍數 }
最後可以寫成如下的形式( % 代表作除法，取餘數的意思)
DP[ i ] = min{ DP[ i // j ] + j， 而且 i % j == 0 }
當 i 是質數的時候，
代表無法從更小的小單元(小單元的長度是n的因數)複製貼上，製造出長度為n的字串。
只能從A開始一個字元一個字元慢慢貼上。
DP[ i ] = 1次複製 + (i-1)次貼上 = i 次操作
最後可以寫成如下的形式
DP[ i ] = i
初始條件(終止條件)為何?
最小規模的問題是
i = 1時，剛好是初始化狀態A，不用任何操作，此時DP[ 1 ] = 0
i = 2時，剛好是初始化狀態A，接著複製A一次，再貼上A一次，此時DP[ 2 ] = 2
程式碼 字串DP
class Solution:
def minSteps(self, n: int) -> int:
# helper lambda function to check if x is multiple of y or not
is_divisible = lambda x, y: x % y == 0
table = {}
def dp(i):
if i in table:
return table[i]
if i == 1:
# Base case:
# "A" is given by initial condition, no extra cost.
table[1] = 0
return 0
elif i == 2:
# Base case:
# "AA" is reached by copy "A" and paste "A"
table[2] = 2
return 2
else:
## General cases:
# Usual case, if i is NOT prime number, we can find a shrink factor F of i, which i is divisible by F, allow us to grow from smaller string by copy-and-paste
# the length of smaller string being copied = i / F
# cost of copy: 1
# cost of paste: F - 1
# total cost = DP[ i / F ] + cost of copy + cost of paste = DP[ i / F ] + 1 + F - 1 = DP[ i / F ] + F
# Worst cast, if i is prime number,
# then "AAA...A" with length i can only reached by copy "A" and paste (i-1) times, total cost = 1 + (i-1) = i
table[i] = min( [i] + [dp(i//factor) + factor for factor in range(2, int(i**0.5)+1 ) if is_divisible(i, factor)] )
return table[i]
# ---------------------------------------------------
return dp(n)
複雜度分析
時間複雜度:O(n^1.5)
雙層迭代，外層迭代index i，內層迭代factor，O(n) * O(n^0.5) = O(n^1.5)
空間複雜度: O(n)
需要建立一個DP table，所需空間為O(n)
