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

Question

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

解决方案确实没有解释.

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

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

Answer 1

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

使用此信息,您可以计算从AB(称为nAB),AC(称为nAC),AD,...等(所有组合对)的路径数.请注意,从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,添加它们.原则上,你然后减去通过这三个路径但没有这些路径的路径.