コンボ数(注記作成)

概念の説明

まず上の写真を調べてみましょう
n=5の場合、r=3を例にとると、以下の事項を表す.

つまり、5つの中から3つを選ぶ方法です.
繰り返し不可能な5の中から3個を抽出するので、以下の3 x 2 x 1を分ける.
では、上記の意識はどのように成り立っているのでしょうか.

n=5、r=3を例にとると、上記のようになります.

なぜなら、状況の数は2つに分けることができるからです.
例えば、5を必ず含む場合、3つの数字を組み合わせると、4つの数字のうち2つの数字しか組み合わさないことを意味する.
逆に、必ずしも5を含むとは限らない場合、4つの数字のうち3つの数字を組み合わせている.
この2つの数字を合わせると5つの数字のうち3つに等しい.

上記の式をDFSと表すとどうなりますか?

n=rまたはr=0の場合、1つしかありません.
DFS(3,3)は三選三という意味で、当然の場合の数は1です.
DFS(1,0)とは、1つから0個を抽出することである.
少し紛らわしいかもしれませんが、0個吸うと何も吸わないのと同じなので、ケースの数は1です.
では、コードで実現しましょう.

function solution(n, r){         
        let answer=[];
        function DFS(n, r){                
            if(n===r || r===0) return 1;
            else return DFS(n-1, r-1) + DFS(n-1,r);                    
        }
        answer=DFS(n, r);
        return answer;
    }
	console.log(solution(5, 3));

n=rまたはr=0の場合、1を返して再帰関数を終了します.
さもないと下に進むので、nとrの数字をそれぞれ消します.
しかし、このコードには問題があります.
nとrが5と3の場合、数字が小さい場合は問題ありませんが、30,25程度の数字であれば、下に伸びる数が非常に多くなります.
すなわち、効率の問題が発生した.

効率の問題をどのように解決しますか?

この問題を解決するために、メモを使います.
注記各DFSの結果値を異なる空間に格納し、同じDFSを繰り返したときに取得することを意味します.

例えば,左側DFS(2,1)の処理が完了した後,2であることに気づいた.
その後右側に同じDFS(2,1)が出てきた場合、さらに下に伸ばさなければなりませんか?
つまり、同じDFSをメモで記録しておけば、この値をさらに下に進むことなく知ることができ、時間を短縮することができる.

上記のように、dyには値が格納され、ロードされる.
dy[n][r]からなる.
では、コードで実現しましょう.

function solution(n, r){         
        let answer=[];
  	let dy = Array.from(Array(35), ()=> Array(35).fill(0));
        function DFS(n, r){ 
            if(dy[n][r]>0) return dy[n][r];
            if(n===r || r===0) return 1;
            else return dy[n][r] = DFS(n-1, r-1) + DFS(n-1,r);                    
        }
        answer=DFS(n, r);
        return answer;
    }
	console.log(solution(5, 3));

dy[n][r]に値がある場合はdy[n][r]を返し、ない場合はdy[n][r]に値を入れる.