问题描述

塔子哥的家乡即将举行一年一度的彩灯节。节日中，塔子哥负责布置一排彩灯，每个彩灯可以选择亮起“红”或“绿”两种颜色，用红色代表喜庆，会增加喜气值；用绿色代表和谐，会增加安宁值。但是为了避免颜色单调，相邻的灯不能亮起相同的颜色。在确保相邻彩灯颜色不同的前提下，塔子哥想知道如何点亮这些彩灯才能使得喜气值和安宁值的总和最大。

题解

简述一下题意，有 $n$ 盏灯，每个灯有两种颜色，每种颜色对应一个权值，可以选择一种颜色点亮，或者不点点，不能有两盏连续的灯颜色相同。

这题是 Leetcode上的 打家劫舍 变形题，是一类动态规划的问题。

定义 $f[i][j]$ 为，考虑前 $i$ 盏灯，且最后一盏灯的状态为 $j \quad j \in [0, 1, 2]$ 的最大权值。

状态转移为：