2 Keys Keyboard

Intuition

Solution

class Solution:
    def minSteps(self, n: int) -> int:
        dp = [[None] * (n + 1) for _ in range(n + 1)]
        dp[1][0] = 0
        for l in range(1, n + 1):
            for p in range(1, l):
                if dp[l - p][p] is not None:
                    dp[l][p] = dp[l - p][p] + 1
            dp[l][l] = min([i for i in dp[l][:l] if i is not None]) + 1
        return min([i for i in dp[n] if i is not None])