划分dp（Python）

参考：https://www.nowcoder.com/share/jump/5537992501767403764056

思路：这题可以用划分dp来做，我们定义表示到使得数组为空的最小划分数，并且记录一个数组，用来记录元素值的最小划分次数。这样后续在进行首尾元素相同，状态转移的时候，就可以找到结尾元素对应的最小划分次数，然后进行划分 + 1，完成状态转移。最终判断一下能否被划分即可，如果可以的话，输出最小划分值；否则输出-1。这个算法可以解决值更大的情况

代码：

import sys
input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

def solve():
    n = II()
    a = [0] + LII()

    dp = [inf] * (n + 1)
    min_cost = [inf] * (max(a) + 1)
    dp[0] = 0

    for i in range(1, n + 1):
        prev = i - 2
        if prev >= 0:
            target = a[prev + 1]
            min_cost[target] = fmin(min_cost[target], dp[prev])

        cur_val = a[i]
        best_prev = min_cost[cur_val]
        if best_prev != inf:
            dp[i] = best_prev + 1

    print(-1 if dp[n] == inf else dp[n])

t = 1
# t = II()
for _ in range(t):
    solve()