linux建设门户网站站长工具大全

题目如下

这个题我一开始是先生成满足0，1，2的全排列，但是n很大时很快就超出内存限制了，后来想到用动态规划的方法做，这里先分析一下。
n=2时，有01，02，10，12，20，21共6项，
n=3时，有010,012,020,021…共12项
容易推导出，n=m时，有3 * Math.pow(2, m-1)项
这里我们先定义一个数组f (n, i)表示第n组中以i结尾的所有数组的权值之和，比如
f(2,0)有10， 20两项，权值之和是1+2=3
f(2,1)有01，21两项，权值之和是1+1=2
同理f(2,2)=3
这几个就是我们的初始条件了
那f(n,0)怎么推到呢，0只能加在1和2的后面，如果加在1后面，如*** 10，增加的权值是1, 如果是增加在2后面，如*** 20，增加的权值是2，假设n-1组中以0结尾的数组有count个，那么增加的权值就是1 * count, 假设n-1组中以2结尾的数组有count个，那么增加的权值就是2 * count, 这里就可以写出推导式f(n,0) = f(n-1) + count * 1 + f(n-2) + 2 * count, 其他也这样推导出来。代码如下

    public int fun (int m) {final int MAX = (int) Math.pow(10, 7);// 容易归纳出// n= 2时，有6个数组// n= 3时，有12个数组// n= m时，有3*math.pow(2,n-1)个数组int[][] array= new int[m+1][3]; // array[n][i]表示第n组以i结尾的数组的权值array[2][0] = 3; // 10,20array[2][1] = 2; // 01,21array[2][2] = 3; // 02,12for (int n = 3; n < m+1; n++) {int count = (int) Math.pow(2, n-2); // n-1组中分别以以0，1，2结尾的各有多少项// 第n组中以0结尾的分别是由上一组中以1和2结尾的组成// 将0添加在1后面权值+1， 共有count项，总权制增加count*1// 将0添加在2后面权值+2， 共有count项，总权制增加count*2， 其他的类推array[n][0] = (count*1 + array[n-1][1]) + (count*2 + array[n-1][2]) % MAX;array[n][1] = (count*1 + array[n-1][0]) + (count*1 + array[n-1][2]) % MAX;array[n][2] = (count*2 + array[n-1][0]) + (count*1 + array[n-1][1]) % MAX;}return (array[m][0] + array[m][1] + array[m][2]) % MAX;}