leetcode 中 Unique Paths 问题可以用C(n,m)求解?

bbaimu
  • 694

1:从左上角出发到右下角,有多少种路径可供选择
图片描述

2:从 m 个数中选出 n个数

这两问题为什么等价

回复
阅读 3k
1 个回答
  • 总步数一定

  • 走法只有两种,非右即下

  • 若将经过的走法“右”及“下”排成一列,则这种序列与路径一一对应

于是此问题等价于:将固定多个“右”和固定多个“下”排成一列,有多少种排法。

设共有 m 个 右,n 个 下,则总数为: C(n, m+n)

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏