字串DP: 用最少的操作次數生成字串_2 Keys Keyboard_Leetcode #650

Kenny Eliason on Unsplash

題目敘述 Leetcode: 650. 2 Keys Keyboard

一開始初始化的時候，記事本上只有一個字元'A'。

只允許下列兩種操作

1. 複製目前記事本上的整個字串。
2. 貼上之前複製的內容，串接在尾端。

請問，最少需要幾個操作，
才能製造出內容都是 "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)

Reference:

[1] 2 Keys Keyboard - LeetCode