房子涂色

一排房子需要涂色，颜色可以选红、绿、蓝，每栋房子涂不同的颜色的费用不同。相邻房子不允许涂相同的颜色。求如何涂色使得涂色总费用最小。

第一行为整数n，表示n栋房子。 第二行至第四行分别为为n栋房子涂红色、绿色、蓝色所需要的费用。涂一个房子的费用不会超过1000

一个整数，表示最小总费用。

数据范围

对于所有的测试点满足 1 \le n\le 10000

y样例1解释

处理第 1 栋房子 第一栋房子没有前置限制，直接取对应颜色的费用： 涂红色：dp[1][0] = 14

涂绿色：dp[1][1] = 11

涂蓝色：dp[1][2] = 14

1. 处理第 2 栋房子 当前房子涂色费用 + 前一栋房子“不同颜色”中的最小费用：

第2栋涂红色（花费2）：前一栋只能涂绿(11)或蓝(14)，取较小值11。dp[2][0] = min(11, 14) + 2 = 11 + 2 = 13

第2栋涂绿色（花费14）：前一栋只能涂红(14)或蓝(14)，取较小值14。dp[2][1] = min(14, 14) + 14 = 14 + 14 = 28

第2栋涂蓝色（花费3）：前一栋只能涂红(14)或绿(11)，取较小值11。dp[2][2] = min(14, 11) + 3 = 11 + 3 = 14

1. 处理第 3 栋房子 同理，将第3栋的费用加上第2栋不同颜色的最小值：

第3栋涂红色（花费11）：前一栋只能涂绿(28)或蓝(14)，取较小值14。dp[3][0] = min(28, 14) + 11 = 14 + 11 = 25

第3栋涂绿色（花费5）：前一栋只能涂红(13)或蓝(14)，取较小值13。dp[3][1] = min(13, 14) + 5 = 13 + 5 = 18

第3栋涂蓝色（花费10）：前一栋只能涂红(13)或绿(28)，取较小值13。dp[3][2] = min(13, 28) + 10 = 13 + 10 = 23

1. 得出最终答案 最后在涂红、涂绿、涂蓝三种情况中取全局最小值：

min(dp[3][0], dp[3][1], dp[3][2]) = min(25, 18, 23) = 18

动规专题