組み合わせの数(DFS)を求めます

6199 ワード
アルゴリズム問題 テキストリンク

質問する


組み合わせの数を求めましょう
5 C 2=1,2,3,4,5から2つの数字を抽出して組み合わせることができる数.조합수의 공식nCr = (n-1)C(r-1) + (n-1)C(r)

コード#コード#

public class CombinationNumber {
    static int[][] memo = new int[35][35];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();
        memo = new int[n+1][n+1];
        System.out.println(dfs(n,r));
    }
    public static int dfs(int n, int r){
        if(n==r || r==0){
            return 1;
        }else{
            if(memo[n][r] != 0) return memo[n][r];
            return memo[n][r] = dfs(n-1, r-1) + dfs(n-1, r);
        }
    }
}

説明:


これはアルゴリズムを用いて組合せ数という数学概念の問題を解決する.あなたはdfsの問題の仕方を把握していると思います.これまで,伸び続けるdfs問題を解くことを主としていたためか,式にdfsを加える方法はすぐには考えられなかった.
組み合わせ数の数学の概念を熟知すればいい.
規則付き数式+規則付き数式=dfs(規則)+dfs(規則)
答え:NODEJS回答REの挿入質問
【詳細な証明過程を含む】カエルは1回に1段の階段を飛び上がることも、2段を飛び上がることもできる.このカエルが1つのn級の階段に飛び上がることを求めて全部で何種類の跳び方があります