返回信息流现在有一个大的square，里面有H行，W列，有一个机器人，从（1,1）这个位置，每次往下或者往右跳一步，但是在左下角的位置，有A*B大小的位置是不能跳的，请问从左上角跳到右下角，需要多少步。
用DP肯定能做出来，就是时间复杂度太高了。请问可以排列组合的方法来做吗？
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #93117同步于 2017/4/25
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
求问一个排列组合的题目
kelvinlu
2017/4/25镜像同步15 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
谢谢大神，ths a lot
【 在 dxy1 的大作中提到: 】
: http://www.mamicode.com/info-detail-1709922.html
不好意思，没看懂你写的啥东西。请问图能够更新一下吗？
【 在 a940100079 的大作中提到: 】
: 设h行w列共有的情况为Chw（所有的位置都能跳）
: 假设4行5列，AB分别为2和3
: 其实就是计算C24*C22+C25*C21
: ...................
除了用枚举之外，还有啥方法可以解决这个题目吗？
【 在 dxy1 的大作中提到: 】
: http://www.mamicode.com/info-detail-1709922.html
4行5列
左下角2行3列不能通过（我用红色表示无法通过的区域）
这个时候如果想从（1，1）走到（4，5）这个位置，有2（2是由5-3计算出来的）种情况
情况一：
从（1，1）这个点走到（2，4）这个点----（2，4），这个多少种情况排列组合你应该会算，假设为X1种方法
（2，4）这个点走到（3，4）这个点，只有1种方法
（3，4）这个点走到（4，5）这个点，假设X2种方法
所以情况一总共有X1*1*X2种方法（路径）
情况二
从（1，1）这个点走到（2，5）这个点----（2，5），这个多少种情况排列组合你应该会算，假设为Y1种方法
（2，5）这个点走到（3，5）这个点，只有1种方法
（3，5）这个点走到（4，5）这个点，假设Y2种方法
所以情况一总共有Y1*1*Y2种方法（路径）
最后的结果就是X1*1*X2+Y1*1*Y2
【 在 kelvinlu 的大作中提到: 】
: 现在有一个大的square，里面有H行，W列，有一个机器人，从（1,1）这个位置，每次往下或者往右跳一步，但是在左下角的位置，有A*B大小的位置是不能跳的，请问从左上角跳到右下角，需要多少步。
: 用DP肯定能做出来，就是时间复杂度太高了。请问可以排列组合的方法来做吗？