字节跳动-第二题公园修路(动态规划)
第一次提交提交的是递归解法，递归解法时间复杂度太高，50%
dp后面改出来的，改完才发现已自动交卷了
N=4个点对他们编号【0，1，2，3】
第一种 0-1连接 前面剩余0个点 1种连接方法，后面剩余2个点 1种连接方法 1*1
第二种 0-3连接 前面剩余2个点 1种连接方法，后面剩余0个点 1种连接方法 1*1
共计2种
N=6个点对他们编号【0，1，2，3，4，5】
第一种 0-1连接 前面剩余0个点 1种连接方法，后面剩余4个点 2种连接方法 2*1
第二种 0-3连接 前面剩余2个点 1种连接方法，后面剩余2个点 1种连接方法 1*1
第三种 0-5连接 前面剩余4个点 2种连接方法，后面剩余0个点 1种连接方法 2*1
共计5种
N个点对他们编号【0，1，2，3，4，5，...，N-1】
第一种 0-1连接 前面剩余0个点 1种连接方法，后面剩余N-2个点 dp[0]*dp[N-2]
第二种 0-3连接 前面剩余2个点 1种连接方法，后面剩余N-4个点 dp[2]*dp[N-4]
第三种 0-5连接 前面剩余4个点 2种连接方法，后面剩余N-6个点 dp[4]*dp[N-6]
......
第三种 0-N-1连接 前面剩余N-2个点，后面剩余0个点 1种连接方法 dp[N-2]*dp[0]
dp[0]=1
dp[2]=1
dp[4]=dp[0]*dp[2] dp[2]*dp[0]
dp[6]=dp[0]*dp[4] dp[2]*dp[2] dp[4]dp[0]
package algorithm.bytecode;
import java.util.Scanner;
public class Second {
static long MOD=1000000007L;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String mStr=in.nextLine();
int m=Integer.valueOf(mStr);
long s1=System.currentTimeMillis();
long r1=solution(m);
long e2=System.currentTimeMillis();
System.out.println(e2-s1);
System.out.println(r1);
long start=System.currentTimeMillis();
long r2=recursiveSolution(m);
long end=System.currentTimeMillis();
System.out.println(end-start);
System.out.println(r2);
}
public static long solution(int n){
if(n==0){
return 1;
}
if(n==2){
return 1;
}
long[] data=new long[n 1];
data[0]=1;
data[2]=1;
for(int i=4;i<=n;i =2){
long temp=0;
for(int j=0;j<i;j =2){
temp=(temp data[j]*data[i-j-2])%MOD;
}
data[i]=temp;
}
return data[n];
}
public static long recursiveSolution(int n){
if(n==0){
return 1;
}
if(n==2){
return 1;
}
long count=0;
for(int i=1;i<n;i =2){
long left=solution(i-1)%MOD;
long right=solution(n-i-1)%MOD;
count=(left*right count)%MOD;
}
return count;
}
}
