文章目录
一、限制条件的非降路径数
一、限制条件的非降路径数
----
从
(0,0)
到
(n,n)
除端点外 , 不接触对角线的非降路径数 ?...此时无法使用基本公式进行处理了 , 必须使用组合对应的思想 ;
上图示例中 , 从
(0,0)
出发到
(n,n)
, 只有两个端点
(0,0)
和
(n,n)
接触了对角线 , 中间的每一步都没有接触该对角线...计算原理 , 先计算对角线下方的非降路径 : 这里只计数在对角线下方的非降路径数 , 因为 对角线上下的非降路径是对称的 , 因此这里 先将对角线下方的非降路径计算出来 ;
对角线下方的非降路径 乘以...2
, 就是总的 不接触对角线的 非降路径数 ;
2 ....这里就得到了一个组合对应关系 :
每条从
(0,1)
出发 , 到
(n, n-1)
的 非降路径 ( 即将 红色的线段 与 剩余的 黑色线段 可以拼接起来的路径 )
都可以与
从
(1,0)