我们先DP分析 dp[i][j]表示,按从左往右的顺序填到i时,有j对相邻数字不同,的方案数 显然:dp[i][j]=dp[i-1][j]*(m-1)+dp[i-1][j-1]; 我们把DP在纸上推演如下: 发现:每个i所在行的d[pi][j]其实就是二次项展开的一项 求和dp[n][0]到dp[n][k]即可。 第二种思路是用组合数直接进行分析: 考虑:n个数,k个相邻位置数相同, 我们在n-1个空位中选择k个位置,使得k左右数相同。 然后固定最左边的数,有m种选法,依次往右选,遇到刚才选出的位置,选法只有一种。 其余都是m-1种选法。 综上方案数为: 同样求和即可。 #include