涂颜色的RPG问题

长度为n的方格，刷3种颜色的颜料，相邻的方格颜料颜色不能相同，且首尾方格颜色不能相同。每个方格必须涂色。计算一共有多少种涂色方式。

解题思路：（1）f(1)=3,f(2)=6,f(3)=6

　　　　（2）如果有n个方格，当对第n个方格填色时，有两种情况：

　　　　　１）应该已经对前面n-1个方格填好了色，有f(n-1)种情况，此时第n-1个跟第一个颜色一定不一样，所以第n个只有一种选择。
　　　　　２）对前面n-2个方格填好色，有f(n-2)种情况，第n-1个空格颜色跟第一个颜色一样（否则就成了上面那种情况了），只有一种可能，最后第n个方格可以填两种颜色（因为n-１和１是第同种颜色），所以是　２*f(n-2);

可以推出f(n)=f(n-1)+2(n-2),n>=4;

long getSolutionNums(int n)

{

    long[] nums = new long[51];

    nums[0] = 3;

    nums[1] = 6;

    nums[2] = 6;

    for(int i = 3; i < n; i++)

        {

        nums[i] = nums[i-1] + 2*nums[i-2];

    }

    return nums[n-1];

}

巴特西

涂颜色的RPG问题

最新文章

热门文章