最近公共祖先_走方格的方案数

走方格的方案数

走方格的方案数

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] array = new int[n+1][m+1];
        //dp动态规划
        //状态定义: 到达(i,j)位置的走法!
        //状态转移方程:f(i,j) = f(i-1,j) + f(i,j-1);
        //初始状态:f(i,0) = 1 ,f(0,j) = 1;
        //返回结果:f(n,m)!!!
        
        //初始化 
        for(int i = 0;i<=n;i++){
            array[i][0] = 1;
        }
         for(int i = 0;i<=m;i++){
            array[0][i] = 1;
        }
        for(int i = 1; i <= n;i++){
            for(int j = 1;j <= m;j++){
                array[i][j] = array[i-1][j] + array[i][j-1];
            }
        }
        System.out.println(array[n][m]);
    }
}

最近公共祖先

最近公共祖先

import java.util.*;
public class LCA {
    public int getLCA(int a, int b) {
        //每次都让较大的节点先找父节点,
        // 直到 a和b相遇!就是公共节点!
        while(a!=b){
            if(a>b){
                a/=2;
            }else{
                b/=2;
            }
        }
        return a;
        
    /*    int[] array1 = new int[a];
        int[] array2 = new int[b];
        int i = 0;
        while(a!=0){
            array1[i++] = a;
            a/=2;
        }
        int j = 0;
        while(b!=0){
            array2[j++] = b;
            b/=2;
        }
        for(int k = 0;k<i;k++){
            for(int z = 0;z<j;z++){
                if(array1[k]==array2[z]){
                    return array1[k];
                }
            }
        }
        return array1[i-1]; */
    }
}