我似乎无法在任何地方找到解决方案。下面给出了问题的描述：
问题陈述
科希马国王为他的行政级别员工预留了一条新的专属街道，他们可以在那里建造自己的房屋。他已指派你规划那条街道。你必须决定允许沿街道的哪些地块建造新建筑物。为此，您首先要计算将免费地块分配给建筑物的可能方式的数量，限制条件是不存在允许建造的两个连续地块 - 您想让居民感觉他们拥有更多腾出房间，让他们可以快乐地生活。这条街被分成M个部分。每个部分对应于两个地块，街道两侧各有一个。找出可能分配的数量。
输入/输出规格
输入规格
在第一行给你 M ( 0 < M ≤ 1000 )。
输出规格 您需要将结果输出到变量 output1。
注意：如果没有可能的解决方案，您需要返回 0 作为输出。
例子
输入：3
输出：25
示例说明：
如果我们只看街道一侧并将 X 标记为允许建造的地块，将 Y 标记为自由地块，我们有：XYX、YXY、YYX、XYY、YYY。
由于另一侧存在相同的数字，因此我们有 5*5 = 25 种组合。
This question can be solved by Dynamic programming. If we store the count of number of X and number of Y, If the end Character is Y then it results in two strings, by appending X and Y at the end, But if the last character is X, then only one string can be generated by appending Y at the end. This gives the answer
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class KingKohima {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int M=Integer.parseInt(br.readLine());
long countX[]=new long[M+1];
long countY[]=new long[M+1];
countX[0]=0; countY[0]=0;
countX[1]=1; countY[1]=1;
countX[2]=1; countY[2]=2;
for(int i=3;i<=M;i++){
countX[i]=countY[i-1];
countY[i]=countX[i-1]+countY[i-1];
}
long finalCount=countX[M]+countY[M];
System.out.println(finalCount*finalCount);
}
}
这个问题与排列和组合特别是二项式定理有关。Scope 是那些擅长于此的人，他们可以得到这个问题的数学方程，然后，很容易将任何 M 作为该方程的输入。
但是通过编码，python 解决方案可以是：
from itertools import product
M = 7 #change as per need
cnt = 0
l = []
for w in product(['x','y'], repeat=M):
tmp = ''.join(w)
if 'xx' not in tmp:
l.append(tmp)
cnt += 1
print cnt*cnt
print l
输出实例：
1156
['xyxyxyx', 'xyxyxyy', 'xyxyyxy', 'xyxyyyx', 'xyxyyyy', 'xyyxyxy', 'xyyxyyx', 'xyyxyyy', 'xyyyxyx', 'xyyyxyy', 'xyyyyxy', 'xyyyyyx', 'xyyyyyy', 'yxyxyxy', 'yxyxyyx', 'yxyxyyy', 'yxyyxyx', 'yxyyxyy', 'yxyyyxy', 'yxyyyyx', 'yxyyyyy', 'yyxyxyx', 'yyxyxyy', 'yyxyyxy', 'yyxyyyx', 'yyxyyyy', 'yyyxyxy', 'yyyxyyx', 'yyyxyyy', 'yyyyxyx', 'yyyyxyy', 'yyyyyxy', 'yyyyyyx', 'yyyyyyy']
所以，这解决了问题。如果大 M 可能有意外的输出，请发表评论。
使用递归。我不确定时间复杂度，因为对于大量输入，它会花费大量时间（实际上对于大值会挂起）。对于小的输入，即 M < 10，这似乎给出了答案。
#include <iostream>
using namespace std;
int recur(char c, int num, int N) {
if (num == N) {
return 1;
}
if (num < N) {
if (c == 'X') {
return recur('Y', num + 1, N);
} else {
return (recur('X', num + 1, N) + recur('Y', num + 1, N));
}
}
}
int main()
{
int N = 4;
//x is number of combinations when the first slot is used to build a house
int x = recur('X', 1, N);
//y is number of combinations when the first slot is left empty
int y = recur('Y', 1, N);
cout << "x = " << x << endl;
cout << "y = " << y << endl;
//Since same number exists on other side also
cout << "total = " << (x + y) * (x + y) << endl;
return 0;
}
我会建议这背后的逻辑。将 X 视为 1，将 Y 视为 0。010 101 000 100 001 是没有两个 1 相邻且总和 = 5 的情况。返回结果 5*5。因此，生成 3 位的二进制数并增加每个此类数字的计数。
如果我们有多个测试用例，那么使用这个解决方案：
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.HashMap;
public class KohimaKing {
static HashMap<Integer,BigInteger> fibboTerm = new HashMap<Integer,BigInteger>();
public static void main(String[] args) throws Exception
{
fibboTerm.put(new Integer(0),new BigInteger("0"));
fibboTerm.put(new Integer(1),new BigInteger("2"));
fibboTerm.put(new Integer(2),new BigInteger("3"));
Integer i=new Integer(3);
for(;i<=1000;i++)
{
fibboTerm.put(i, fibboTerm.get(i-2).add(fibboTerm.get(i-1)));
}
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter sections");
int m = Integer.parseInt(br.readLine());
System.out.println(fibboTerm.get(m).multiply(fibboTerm.get(m)));
}
}
我认为递归将是解决这个问题的最佳方法。我的想法是考虑一棵可以形成深度为 M 的树，最后计算树中叶节点的数量。这只是一个想法，实际的递归可以通过思考第一个位置是否可以取 X 来开始。仅当它的父级（上一个情节）采用 Y 时，它才能同时采用 X 和 Y。但如果它的父级采用 X，它只能采用 Y。有了这个想法，我做了一个递归。
int count=0; //Maintain a global counter to count the leaves
void fun(bool xTaken, int M)
{
if(M==0)
{
count++; //We've reached the leaf
return;
}
if(xTaken==false)
{
//We can take X
fun(true,M-1);
//or we can take Y
fun(false,M-1);
}
else if(xTaken==true)
{
//We can only take Y
fun(false,M-1);
}
}
我们的答案将是count*count。同样，我们可以通过使用 memoization 处理重复递归来优化此递归
package HackerRank;
import java.io.IOException;
import java.util.Scanner;
class Tester1KingKohm {
public static void plotmaker(int input) {
int i = 1;
int countx = 1;
int county = 1;
while (i <= input) {
if (i > 1) {
int tempx = countx;
countx = county;
county = tempx + county;
}
i++;
}
System.out.println(countx + " " + county);
int total = countx + county;
int bothsidetotal = total * total;
System.out.println(bothsidetotal);
}
public static void main(String[] args) throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
plotmaker(sc.nextInt());
}
}
我认为，这个公式可能会给出问题的答案
对于 M 个部分，X 和 Y 的可能组合总数为 2^M，但我们必须扣除以下情况：1）两个 X 在一起 2）三个 X 在一起 3）四个 X 在一起等等......直到 M X 在一起。
计数 = 2^M - (1! + 2! + 3!.........M-1!)
最终答案 = 计数 * 计数
我不确定这是否是最有效的解决方案，但是对于给定的值 m，所需安排的总数是：
r=1;sum=0;
while(m>=r)
{
sum+=mCr;
m--;
r++;
}
例如，如果 m=7 ans= 7C1 + 6C2 + 5C3 + 4C4 ；
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.HashMap;
public class KingKohima
{
public static void main(String[] args) throws Exception
{
BigInteger a = new BigInteger("2");
BigInteger b = new BigInteger("3");
BigInteger result = new BigInteger("0");
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
int m = Integer.parseInt(br.readLine());
if(m<=0)
{
System.out.println("0");
}
else if(m==1)
{
System.out.println("2");
}
else if(m==2)
{
System.out.println("3");
}
else
{
Integer i=new Integer(3);
for(;i<=m;i++)
{
result = a.add(b);
a=new BigInteger(b.toString());
b=new BigInteger(result.toString());
}
}
System.out.println(result.multiply(result));
}
}