这道dp的思路比较巧妙,题目要求我们最后的数字需要满足下面两个条件
1.它的数字只包含 0,1,2,3,且这四个数字都出现过至少一次。
2.所有的 0 都出现在所有的 1 之前,而所有的 2 都出现在所有的 3 之前。
我们先暂且不看第一个条件,在满足第二个条件的情况下,假设我们当前数字为n位的,总共有下面六种情况:
(1)数字中只包含 2 。没有出现过0、1、3
(2)数字中只包含 2,0。没有出现过1、3
(3)数字中只包含 2,3。没有出现过0、1
(4)数字中只包含 0,1,2 。没有出现过3
(5)数字中只包含 0,2,3。没有出现过1
(6)数字中2,0、1、3全部包含
为什么只有上面六种状态,希望不理解的同学拿纸笔枚举一下就懂了,以第一个为例,因为要满足0 都出现在所有的 1 之前,而所有的 2 都出现在所有的 3 之前。所以只能选 0 和 2,但是因为只有一个数字,最高位不能是0(题目要求),只能是2。其他五种状态类似。
然后知道了n位数字只有上面六种状态之后,假设现在我们需要计算n+1位数字的状态
以第六种状态为例,因为只增加了一位数字,所以第六种状态0、1、2、3只能从第4、5、6这三种状态转换过来
(1)第四种状态0、1、2再加上第n+1位数字取3,转换为第六种状态
(2)第五种状态0,2,3再加上第n+1位数字取1,转换为第六种状态
(3)第六种状态,因为只需要满足0在1前面,2在3前面,因此n+1可以取2和3,有两种情况。
即对应着我们的代码dp6 = dp4 + dp5 + dp6 * 2。
到这里大家好好思考一下就能得出结果啦,不用二维数组记得倒序更新噢。拜拜~~
Java代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
long dp1 = 0;//只有2,剩 0 1 3
long dp2 = 0;//只有 2 0 剩1 3
long dp3 = 0;//只有 2 3 剩0 1
long dp4 = 0;//只有0 1 2 剩3
long dp5 = 0;//只有0 2 3 剩1
long dp6 = 0;//都有
for(int i = 1 ; i <= n ; i++){
dp6 = (dp4 + dp5 + dp6 * 2) % 1000000007;
dp5 = (dp2 + dp3 + dp5 * 2) % 1000000007;
dp4 = (dp2 + dp4 * 2) % 1000000007;
dp3 = (dp1 + dp3) % 1000000007;
dp2 = (dp1 + dp2 * 2) % 1000000007;
dp1 = 1;
}
System.out.println(dp6);
}
}