[PHP][アルゴリズム] N人の人気投票順位予想でM人を的中させるパターン数

職場の人に考えてみてと言われたので解いてみました。

解法

動的計画法で出しました。
N人からM人一致させるパターンをdp[n][m]として考える。
1. n=mの時は全的中なので1パターン
2. m=0の時は全パターンからm>=1のパターンを引く
3. それ以外の時は(nからm人決める組み合わせ数) × （残りのn-m人から一人も選ばない組み合わせ数( = dp[n-m][0])）

計算量

O(N^2)。

コード

<?php
$combi = [];
$perm = [];
$dp = [];

solve(9);

/**
 * N人で人気投票順位を0~N人一致させるパターン数を計算して表示
*/
function solve(int $size) {
  makeCombination($size);
  makePermutation($size);

  for ($i=1; $i <= $size; $i++) {
    for ($j=0; $j <= $i; $j++) {
      printf("%d人から%d人一致するパターン数: %d\n", $i, $j, rec($i, $j));
    }
  }
}

/**
 * 動的計画法でN人で人気投票順位をM人一致させるパターン数を求める
*/
function rec(int $n, int $m): int {
  global $dp, $perm, $combi;
  assert($n >= $m);

  if (!isset($dp[$n][$m])) {
    if ($n == $m) {
      $dp[$n][$m] = 1;
    }
    else if ($m == 0) {
      // 直接求めるのは大変なので全パターンからm>=1のパターンを引く
      $result = $perm[$n];
      for ($i=1; $i <= $n; $i++) {
        $result -= rec($n, $i);
      }

      $dp[$n][$m] = $result;
    }
    else {
      // 当たっているm個を決める
      $result = $combi[$n][$m];
      // 残りはn-m個から0人一致
      $result *= rec($n - $m, 0);
      $dp[$n][$m] = $result;
    }
  }

  return $dp[$n][$m];
}

/**
 * 組み合わせを計算
 */
function makeCombination(int $size) {
  global $combi;

  for ($i = 0; $i <= $size; $i++) {
    $combi[$i][0] = 1;
  }

  for ($i = 1; $i <= $size; $i++) {
    $combi[0][$i] = 0;
  }

  for ($i = 1; $i <= $size; $i++) {
    for ($j = 1; $j <= $size; $j++) {
      $combi[$i][$j] = $combi[$i-1][$j-1] + $combi[$i-1][$j];
    }
  }

}

/**
 * 順列を計算
 */
function makePermutation(int $size) {
  global $perm;

  $perm[1] = 1;
  for ($i=2; $i <= $size; $i++) {
    $perm[$i] = $perm[$i-1] * $i;
  }
}

パッと浮かんだのがこれだったから書いたけど、もっとスマートな方法がある気もする...
（あとPHPでグローバル変数初めて使ったので、globalっていうキーワードが必要なのを初めて知った）