グリッド経路の数え上げ

グリッド経路の数え上げ

右または下への移動のみを使って、長方形グリッド上の経路の数を数えます。

このチャレンジで学べること

グリッドの左上隅から開始し、rows 行 × columns 列のセルで構成されるグリッド上を、セルの辺に沿ってのみ移動します。一度に右または下へ1辺だけ進み、右下隅に到達するまで繰り返します。異なる移動順序の経路の総数を数えてください。グリッド内に障害物はありません。

2行3列のセルからなるグリッドでは、下方向への移動が2回、右方向への移動が3回必要です。

lattice_paths(rows, columns) を実装してください。

rows: セルの行数（頂点数ではありません）。

columns: セルの列数（頂点数ではありません）。

左上隅から右下隅までの経路の総数を返してください。

0 ≤ rows, columns ≤ 30 かつ rows + columns ≤ 60。いずれかの次元が0の場合は直線経路のみ。0 × 0 グリッドの場合は空の経路が1つ存在します。経路数は符号付き64ビット整数に収まります。

例 1

入力：
rows = 2
columns = 3

期待される出力：
expected = 10

入力：
long long rows = 2;
long long columns = 3;

期待される出力：
long long expected = 10;

入力：
long rows = 2;
long columns = 3;

期待される出力：
long expected = 10;

すべての経路は5回の移動からなります。そのうち2回を下方向に選ぶ方法は10通りあり、10種類の異なる経路が存在します。

例 2

入力：
rows = 0
columns = 4

期待される出力：
expected = 1

入力：
long long rows = 0;
long long columns = 4;

期待される出力：
long long expected = 1;

入力：
long rows = 0;
long columns = 4;

期待される出力：
long expected = 1;

右方向に4回進むだけの直線経路が1つだけ存在します。

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

各経路は、必要な down と right の並び替えにすぎない。

ヒント 2

1種類の移動を、全移動の中のどの位置に置くかを数えればよい。1本ずつ経路探索しない。

ヒント 3

退化したグリッドに注意。どちらかの次元が0なら直進ルートは1通り、0×0 でも空のルートが1通りある。

目安の計算量

時間 O(min(rows, columns))、追加メモリ O(1)

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。