海洋优质的网站建设,上海品牌策划设计,产品软文范例100字,天河建设网站平台题目如下 这个题我一开始是先生成满足0#xff0c;1#xff0c;2的全排列#xff0c;但是n很大时很快就超出内存限制了#xff0c;后来想到用动态规划的方法做#xff0c;这里先分析一下。 n2时#xff0c;有01#xff0c;02#xff0c;10#xff0c;12#xff0c;2…题目如下 这个题我一开始是先生成满足012的全排列但是n很大时很快就超出内存限制了后来想到用动态规划的方法做这里先分析一下。 n2时有010210122021共6项 n3时有010,012,020,021…共12项 容易推导出nm时有3 * Math.pow(2, m-1)项 这里我们先定义一个数组f (n, i)表示第n组中以i结尾的所有数组的权值之和比如 f(2,0)有10 20两项权值之和是123 f(2,1)有0121两项权值之和是112 同理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[m1][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 m1; n) {int count (int) Math.pow(2, n-2); // n-1组中分别以以012结尾的各有多少项// 第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;}
