Back to Leetcode

Readme

LCCUP/2020Fall/LCP25.古董键盘/Readme.md

latest507 B
Original Source

LCP25.古董键盘

令dp[i][j]表示前i个敲击使用了前j种字符的方案数。

为了计算dp[i][j],我们考虑第j种字符在前i次敲击里占了几次?假设是t,那么我们需要制定这t次敲击的位置,那就是comb[i][t].只要确定了这t个位置,剩下的位置就完全等效于在i-t次敲击里使用j-1个字符。所以转移方程式:

cpp
  for (int t = 0; t <= min(i, k); t++)
  {
      dp[i][j] += dp[i-t][j-1] * comb[i][t];                    
  }