Lintcode Problem 4-keys-keyboard with path printing

4-keys-keyboard.py

class Solution:
    """
    @param N: an integer
    @return: return an integer
    """
    def maxA(self, N):
        # write your code here
        dp = [0] * (N)
        pi = [0] * (N)
        dp[0], pi[0] = 1, 'A'
        
        for i in range(1, N):
            dp[i] = dp[i - 1] + 1
            pi[i] = 'A'
            for j in range(i - 3):
                dp[i] = max(dp[i], dp[j] * (i - j - 1))
                if dp[i] == dp[j] * (i - j - 1):
                    pi[i] = j
        
        path = []
        k, last = N - 1,  pi[N - 1]
        while k >= 0:
            if last != 'A':
                if k == last:
                    last = pi[k]
                    path[-2] = 'Ctrl + C'
                    path[-1] = 'Ctrl + A'
                if last == 'A':
                    path.append('A')
                else:
                    path.append('Ctrl + V')
            else:
                path.append('A')
            k -= 1
        
        print(path[::-1])

        return dp[N - 1]