题目描述

小美经常去美团上点外卖，她给自己规划了每天会在哪些商家中选择一家来点。

由于怕吃腻，小美决定不会连续两天点同一个商家。现在请你判断小美有多少种不同的选择方案？

题解

这是道比较经典的线性DP问题，当前的决策与上次决策有关，是 打家劫舍 的变形题

定义 $dp[i][j]$ 表示，当前考虑到第 $i$ 个数，且上一次选的字母是 $j$ 的所有合法方案数。

状态转移为： $dp[i][j] = \sum_{k \neq j} dp[i-1][k]$。

即前 $i$ 天选择字符 $j$ 对应商家的方案数,等于前 $i-1$ 天选择除 $j$ 以外任意字符的方案数之和。