蚂蚁3.28算法笔试第三题

题目描述：
数组染色
数组相邻的三个元素不能同时染色，也不能一个也不染色。
求染色元素的最大和

dp[i][0]  定义为位置i不染色，i - 1也不染色
dp[i][1]= 定义为位置i不染色，i - 1染色
dp[i][2] = 定义为位置i染色，i - 1不染色
dp[i][3] = 定义为位置i染色，i - 1也染色

def dp_color(nums):
    n = len(nums)
    dp = [[0, 0, 0, 0] for _ in range(n)]
    dp[0][2] = nums[0]
    dp[0][3] = nums[0]

    dp[1][1] = nums[0]
    dp[1][2] = nums[1]
    dp[1][3] = nums[0] + nums[1]

    for i in range(2, n):
        dp[i][0] = dp[i - 1][1]
        dp[i][1] = max(dp[i - 1][2], dp[i - 1][3])
        dp[i][2] = nums[i] + max(dp[i - 1][0], dp[i - 1][1])
        dp[i][3] = nums[i] + dp[i - 1][2]
    return max(dp[n - 1])