动态编程算法:在网格上行走

为即将到来的考试提供了一些练习题.我已经给出了这个问题的解决方案,这里描述了这个问题

解决方案确实没有解释.

我很好奇我怎么能在这里得到答案.我想我可以创建一堆子问题

从A-> C,A-> D,A-> E遍历,然后基于先前的解决方案得出A-> B.但我很失落.

首先,只使用R = right和U = up步骤从(0,0)到(x,y)的方法有多少? (没有限制不通过其他点.)每个这样的路径都有长度x y并且包含x R和y U,所以有binom(x y,x)或binom(x y,y)这样做.

使用此信息,您可以计算A-B(称为nAB),A-C(称之为nAC),A-D,…等(所有组合对)的路径数.请注意,从C到D没有路径(因为你不能下去),没有从D到C的路径,因为你不能向左走.

现在,使用包含排除.这个想法是减去坏情况.例如,一个不好的案例将从A开始经过C然后再到B.这可以做多少种方法? nAC x nCB.另一个不好的情况是通过E,有nAE x nEB方法可以做到这一点……减去它们.然后经历D也很糟糕.有一些nAD x nDB方式最终在B处通过E …减去那些.现在,问题是你已经减去了太多(经历了2个坏点的路径)……所以重新加入.有多少点通过C和E并结束于B? nAC x nCE x nEB,添加那些.经过D和E多少分? nAD x nDE x nEB,添加它们.原则上,你然后减去通过这三个路径但没有这些路径的路径.

相关文章
相关标签/搜索