“不过也无所谓，我觉得我不会输，这样，我们各写一组数组(l1,l2)和(b1,b2)，分别组成l1 * b1,l2 * b2 的格子，然后计算，看谁先算出两个，一局定胜负，可以吧？”。
“嗯，很公平，我没问题，开始吧。” 八哥胸有成竹。
走方格（走法数量）不一会儿，两人都把纸条写好了。
摊开纸条
罗拉写的是(3,6)
八哥写的是(7,5)
“我们现在要计算3 * 7 ,6 * 5的方格走法，即使开始”。罗拉说完，拿起纸笔，画了起来，赢在了起跑线。
30秒后
“嘿嘿，分别为 28 和 126”，不到一分钟，八哥边说出了答案。
“你瞎说的吧，我第一个都还没算完呢，你两个都完了？”
“山人自有妙计，你输了”
“等我算完再说，谁知道你的对的还是错的？”
“可是你要是自己算错了或算很久那不是浪费时间？”
“不然捏，我总得验证结果吧？”罗拉忍不住翻白眼。
“看你画了这么多图，挺辛苦的，动动脑子，我要是在你公司，今天这游戏就通杀了？”
“咦，难道有规律？”罗拉自动忽略八哥的后半句话。
“你三天前怎么赢得我的旧币的？你想想？”
“赢钱？打赌啊，不对，难道是动态规划？”
“是啊，你怎么每次都得提醒才想得起来啊”八哥无奈道。
“谁知道你连这都埋个坑？行了，我知道接下来该分析分析了。”
“假设到最右下角的方式有f(n),由于只能往左边或下面走，所以f(n)=f(上边)+f(左边)”
“嗯...其实用二维数组表示好像更好，应该表示为dp[x][y]=dp[x-1][y]+dp[x][y-1]”
“接下来就是子问题的计算，直到边界”
“这里的边界，应该是有沿着墙边走，因为只能向左或向右，所以dp[x][0]=0,dp[0][y]=0”
“接下来代码实现”
“咦你的答案没错诶。不对，你没写代码，而且一分钟都不到，这肯定不是最快的。”罗拉突然醒悟。
“对于这个题目，当然不是最快的，你想一下，对于n * m的格子，我一共要走多少步？向上多少，向下多少？”
“向下是n-1，向右是m-1,一共是m + n - 2,可是这个和你算得快没啥关系吧？”罗拉不解
“谁说没关系，一共m + n - 2,我只要确定向下或向右走的，另一个方向的是不是也确定了？换言之，就是m + n - 2中选n - 1 或 m - 1吧，你发现了什么？”
“从总数里面选出某些...吖，是排列组合的组合，这是一个数学问题”罗拉恍然大悟。
“是的，这里可以看成是组合问题，通过组合共识，10以内的分分钟就算出来了不过分吧，你甚至可以试着代码实现”八哥得意说道
“行吧，我试试，你就是想我写代码吧，我想一下组合公式组合数计算方法，从N项中选出M项:f(n,m) = n! / ((n - m)! * m!) ”
“代码就是这样”
public class WalkGrid { public static void main(String[] args) { System.out.println("3*7方格走法共有：" + cal(3, 7) + " 种"); System.out.println("5*6方格走法共有：" + cal(5, 6) + " 种"); } public static int cal(int n, int m) { int tot = m + n - 2; int res = 1; int max = Math.max(m - 1, n - 1); //公式中tot！与max！部分可以抵消max！部分，减少计算量 for (int i = tot; i > max; i--) res *= i; for (int i = 1; i <= tot - max; i++) res /= i; return res; } } //输出结果 3*7方格走法共有：28 种 5*6方格走法共有：126 种公式中的f(n,m) = n! / ((n - m)! * m!)
可以化简为f(n,m) = n*(n-1)*(n-2)...*(m+1) / (n - m)! 就是代码中max优化的原理
“算我输了，你宝贝等下就还你，话说这个岂不是用数学方法更快？”罗拉赌品还是可以的。
“所以我说了对于这个问题是个样啊，我只要稍微变化一下，公式就不好使了”
“是吗？举个栗子看看” 罗拉来了兴趣。
“行，看在你赌品不错的份上，举了例子”
走格子最短路径“从前有个公主，被魔王抓了，关在魔窟”
“一个勇敢王子准备前往魔窟营救公主，这个过程充满危险，稍有不慎就会有生命危险。”
“魔王在王子的必经之路上布满了陷阱，每一个陷阱都会对王子造成伤害，地图如下所示”