网易 2022-3-27

package org.oj01;

import java.util.*;

public class Main {

    static int res=Integer.MAX_VALUE;
    static int nn;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);

        int a=sc.nextInt();int b=sc.nextInt();int x=sc.nextInt();int y=sc.nextInt();

        dfs(a,b,x,y,0);

        System.out.println(res);

    }

    public static void dfs(int a,int b,int x,int y,int cnt){
        if(a<=0&&b<=0){
            System.out.println("cnt"+cnt);
            res=Math.min(res,cnt);
        }
        else if(a>0&&b<=0){
            dfs(a-x,b,x,y,cnt+1);
        }
        else if(b>0&&a<=0){
            dfs(a,b-x,x,y,cnt+1);
        }
        else{dfs(a-y,b-y,x,y,cnt+1);}
    }

}

第二道dp

import java.util.*;

public class Main {

    static int res=Integer.MAX_VALUE;
    static int nn;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        int n=s.length();
        int[] dp=new int[n+1];
        dp[0]=0;
        if(s.charAt(0)==s.charAt(1)||Math.abs(s.charAt(1)-s.charAt(0))==1){
            dp[1]=s.charAt(0)-'a'+1+s.charAt(1)-'a'+1;
        }
        System.out.println(dp[1]);
        for(int i=2;i<n;i++){
            if(s.charAt(i)==s.charAt(i-1)||(s.charAt(i)-s.charAt(i-1)==1)){
                dp[i]=dp[i-2]+s.charAt(i)-'a'+1+s.charAt(i-1)-'a'+1;
            }else{
                dp[i]=dp[i-1];
            }
        }
        for(int i=0;i<n;i++){
            System.out.print("dp[i]"+dp[i]+" ");
        }
        System.out.println(dp[n-1]);
    }
}

package org.oj01;

import java.util.*;

public class Main {

    static int res=Integer.MAX_VALUE;
    static int nn;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        nn=n;

        TreeNode root=build(n);
        System.out.println(root);
        //bfs
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node==null){
                continue;
            }
            System.out.print(node.val+" ");
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }

    }

    public static TreeNode build(int cur){
        if(cur<=0||cur>nn){
            return null;
        }
        TreeNode root;
        if(cur%2==0){
            root=new TreeNode(cur/2);
            root.left=build(cur/2-1);
            root.right=build(cur/2+1);
        }else{
            root=new TreeNode(cur/2+1);
            root.left=build(cur/2);
            root.right=build(cur/2+2);
        }
        return root;
    }

}
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val=val;
    }
    public TreeNode(int val,TreeNode left,TreeNode right){
        this.val=val;
        this.left=left;
        this.right=right;
    }
}

package org.bd;

import java.util.Scanner;

public class Main {

    static int[] dx={0,1,0};
    static int[] dy={1,0,-1};
    static int res=Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();int m=sc.nextInt();
        int[][] matrix=new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                matrix[i][j]=sc.nextInt();
            }
        }
        boolean[][] vis=new boolean[n][m];

        dfs(matrix,0,0,n,m,0,vis);
        System.out.println(res);
    }
    public static void dfs(int[][] matrix,int start,int end,int n,int m,int cost,boolean[][] vis){
        if(start==n-1&&end==m-1){
            res=Math.min(res,cost);
        }
        if(cost>res){
            return;
        }
        vis[start][end]=true;
        for(int k=0;k<3;k++){
            int a=start+dx[k];
            int b=end+dy[k];
            if(a<0||a>=n||b<0||b>=m||vis[a][b]){
                continue;
            }
            if(matrix[start][end]==matrix[a][b]){
                cost+=1;
                vis[a][b]=true;
                dfs(matrix,a,b,n,m,cost,vis);
                vis[a][b]=false;
                cost-=1;
            }else{
                cost+=2;
                vis[a][b]=true;
                dfs(matrix,a,b,n,m,cost,vis);
                vis[a][b]=false;
                cost-=2;
            }

        }
    }
}