转跳到内容

(红包)算法挑战一则——到达终点的方法种类


只显示该作者

只有该作者的内容显示中。 返回到主题

推荐贴

7 小时前,reflectK说道:

第一题应该可以有结论

第二题只需要dp方程就可以了

那就是两个函数:f(m,n)是走一个mXn网格的路径数,g(m,n,x,y)是走一个mXn网格但不经过点(x,y)的路径数。那么f(m,n)=C(m+n,m),而g(m,n,x,y)=f(m,n)-f(x,y)*f(m-x,n-y)。

那后三个就是

1. f(x,y)*f(x'-x,y'-y)*f(m-x',n-y')+g(m,n,x,y)

2. f(x,y)*f(m-x',n-y')+g(m,n,x,y)

3. f(m,n)-f(x,y)*f(x'-x,y'-y)*f(m-x',n-y')

反倒是魔法那个麻烦点,干脆想成mXnX3三层立体的。从中间层开始,上面那层整体向上移一格,下面那层整体向右移一格,然后就正常DP~

,由fangaa修改
链接到点评
  • 骚男锁定了本主题
游客
此主题已关闭。
×
×
  • 新建...

重要消息

为使您更好地使用该站点,请仔细阅读以下内容: 使用条款