class Solution:

    def minimumMoves(self, A: List[int]) -> int:

        N = len(A)

        dp = [[0] * (N+1) for _ in range(N+1)]

        for i in range(N+1):

            dp[i][i] = 1

        for size in range(2, N+1):

            for i in range(N - size + 1):

                j = i + size - 1

                dp[i][j] = 1 + dp[i+1][j]

                if A[i] == A[i+1]:

                    dp[i][j]  = min(dp[i][j] , 1 + dp[i+2][j])

                for k in range(i+2, j+1):

                    if A[i] == A[k]:

                        dp[i][j]  = min(dp[i][j] , dp[i+1][k-1] + dp[k+1][j])

        return dp[0][N-1]