字节跳动-第二题公园修路(动态规划)

第一次提交提交的是递归解法，递归解法时间复杂度太高，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;

    }

}