package org.example.oj;

import java.util.Stack;

/**
 * 暴力递归  对数器对拍
 */
public class Main {

    public static void main(String[] args) {
        int len=10;
        int max=10;
        int testTime=10000;
        for(int i=0;i<testTime;i++){
            int[] arr=generateRandomArray(len,max);
            int aim=(int)(Math.random()*3*max)+max;
            if(way1(arr,aim)!=way2(arr,aim)){
                System.out.println("ooops!");
                break;
            }
        }
    }

    public static int[] generateRandomArray(int len,int max){
        int[] arr=new int[(int)(Math.random()*len)+1];
        for(int i=0;i<arr.length;i++){
            arr[i]=(int)(Math.random()*max)+1;
        }
        return arr;
    }
    public static int way1(int[] arr,int aim){
        return way(arr,0,aim);
    }
    //对于多元一次方程暴力
    public static int way(int[] arr,int index,int rest){
        if(index==arr.length){
            return rest==0? 1:0;
        }
        int ways=0;
        for(int zhang=0;arr[index]*zhang<=rest;zhang++){
            ways+=way(arr,index+1,rest-arr[index]*zhang);
        }
        return ways;
    }
    public static int way2(int[] arr,int aim){
        if(arr==null||arr.length==0){
            return 0;
        }
        int N=arr.length;
        int[][] dp=new int[N+1][aim+1];
        dp[N][0]=1;
        for(int index=N-1;index>=0;index--){
            for(int rest=0;rest<=aim;rest++){
//                int ways=0;
//                for(int zhang=0;arr[index]*zhang<=rest;zhang++){
//                    ways+=dp[index+1][rest-zhang*arr[index]];
//                }
//                dp[index][rest]=ways;
                //进行优化
                dp[index][rest]=dp[index+1][rest];
                if(arr[index ]<=rest){
                    dp[index][rest]+=dp[index][rest-arr[index]];
                }
            }
        }
        return dp[0][aim];
    }


    //改成dp[][][]
    public static long processDP(int N,int M,int row,int col,int rest){
        int[][][] dp=new int[N][M][rest];
        //对于外面的都是0
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                dp[i][j][rest]=1;
            }
        }
        for(int step=1;step<=rest;step++){
            for(int i=0;i<N;i++){
                for(int j=0;j<M;j++){
                    dp[i][j][step]=dp[i-1][j][step-1]+dp[i+1][j][step-1]+dp[i][j-1][step-1]+dp[i][j+1][step-1];
                }
            }
        }
        return dp[row][col][rest];
    }

    public static long process(int N,int M,int row,int col,int rest){
        if(row<0||row==N||col<0||col==M){
            return 0;
        }
        if(rest==0){
            return 1;
        }
        long res=process(N,M,row-1,col,rest-1);
        res+=process(N,M,row+1,col,rest-1);
        res+=process(N,M,row,col-1,rest-1);
        res+=process(N,M,row,col+1,rest-1);
        return res;
    }



    //通过递归方式棋盘跳跃
    public static int jump(int start,int end,int step){
        if(start<0||start>8||end<0||end>9){
            return 0;
        }
        if(step==0){
            return (start==0&&end==0)? 1:0;
        }
        return jump(start-2,end-1,step-1)+jump(start-2,end+1,step-1)+
                jump(start-1,end-2,step-1)+jump(start-1,end+2,step-1)+
                jump(start+1,end-2,step-1)+jump(start+1,end+2,step-1)+
                jump(start+2,end-1,step-1)+jump(start+2,end+1,step-1);
    }

    public static int dpways(int x,int y,int step){
        if(x<0||x>8||y<0||y>9||step<0){
            return 0;
        }
        int[][][] dp=new int[9][10][step];
        dp[0][0][0]=1;
        for(int h=1;h<=step;h++){
            for(int r=0;r<9;r++){
                for(int c=0;c<10;c++){
                    dp[r][c][h]+=getValue(dp,r-1,c+2,h-1);
                    dp[r][c][h]+=getValue(dp,r+1,c+2,h-1);
                    dp[r][c][h]+=getValue(dp,r+2,c+1,h-1);
                    dp[r][c][h]+=getValue(dp,r+2,c-1,h-1);
                    dp[r][c][h]+=getValue(dp,r+1,c-2,h-1);
                    dp[r][c][h]+=getValue(dp,r-1,c-2,h-1);
                    dp[r][c][h]+=getValue(dp,r-2,c-1,h-1);
                    dp[r][c][h]+=getValue(dp,r-2,c+1,h-1);
                }
            }
        }
        return dp[x][y][step];
    }
    public static int getValue(int[][][] dp,int row,int col,int step){
        if(row<0||row>8||col<0||col>9){
            return 0;
        }
        return dp[row][col][step];
    }

    //将对应的数组字符串转为对应的26个字母
    public static int process(char[] str,int i){
        if(i==str.length){
            return 1;
        }
        if(str[i]=='0'){
            return 0;
        }
        if(str[i]=='1'){
            int res=process(str,i+1);
            if(i+1<str.length){
                res+=process(str,i+2);
            }
            return res;
        }
        if(str[i]=='2'){
            int res=process(str,i+1);
            if(i+1<str.length&&(str[i+1]>='0'&&str[i+1]<='6')){
                res+=process(str,i+2);
            }
            return res;
        }
        return process(str,i+1);
    }

    //通过递归的方式逆置栈
    public static void reverse(Stack<Integer> stack){
        if (stack.isEmpty()) {
            return;
        }
        int i=f(stack);
        reverse(stack);
        stack.push(i);
    }
    //通过递归的方式获得栈底元素
    public static int f(Stack<Integer> stack){
        int result=stack.pop();
        if (stack.isEmpty()) {
            return result;
        }else{
            int last=f(stack);
            stack.push(last);
            return last;
        }
    }

    //将递归改成dp
    public static int dp(int[] arr){
        if(arr==null||arr.length==0){
            return 0;
        }
        int[][] f=new int[arr.length][arr.length];
        int[][] s=new int[arr.length][arr.length];
        for(int i=0;i<arr.length;i++){
            f[i][i]=arr[i];
        }
        int row=0;
        int col=1;
        while(col<arr.length){
            int i=row;
            int j=col;
            while(i<arr.length&&j<arr.length){
                f[i][j]=Math.max(arr[i]+s[i+1][j],arr[j]+s[i][j-1]);
                s[i][j]=Math.min(f[i+1][j],f[i][j-1]);
                i++;
                j++;
            }
            col++;
        }
        return Math.max(f[0][arr.length],s[0][arr.length]);
    }

    public static int win1(int[] arr){
        if(arr==null||arr.length==0){
            return 0;
        }
        return Math.max(f(arr,0,arr.length-1),s(arr,0,arr.length-1));
    }
    //定义先手函数
    public static int f(int []arr,int left,int right){
        if(left==right){
            return arr[left];
        }
        return Math.max(arr[left]+s(arr,left+1,right),arr[right]+s(arr,left,right-1));
    }
    //定义后手函数
    public static int s(int[] arr,int left,int right){
        if(left==right){
            return 0;
        }
        return Math.min(f(arr,left+1,right),f(arr,left,right-1));
    }
}