有这么一题, 一个人从A到C, 一定要经过B, 并且每次走一步向东或者向北, 不能回头, 问一共有多少不同的方法.
暴力搜索(穷举)
理论上说, 你可以用暴力列举所有从A到C的走法 然后再一一比较是否经过B, 不过这种方法很低效因为需要列举出所有走法. 如果水平有X步垂直有Y步那么一共的方案有:
可以这么理解, 一共有 x+y 步 选其中 x 或者 y 步来往东或者往北走.
纯数学方法: 排列组合
细想一下, 我们只要分两个阶段即可: 第一个阶段计算由A到B的方法数, 第二个阶段计算由B到C的方法数, 然后这么一乘就是最后的方案数了.
根据本题, 最终方案为
递归
假设我们定义了 f(x, y) 用于计算 水平x步, 垂直y步的方案数: 那么:
1 2 3 4 5 6 | function f($x, $y) { if (($x == 0) || ($y == 0)) { return 1; } return f($x - 1, $y) + f($x, $y - 1); // 每次两种选择: 往东1步或者往北一步 } |
function f($x, $y) { if (($x == 0) || ($y == 0)) { return 1; } return f($x - 1, $y) + f($x, $y - 1); // 每次两种选择: 往东1步或者往北一步 }
最终答案就是:
1 | echo f(3, 4) * f(5, 5); // 8820 |
echo f(3, 4) * f(5, 5); // 8820
这里的递归写法可以认动态规化的一种, 退出条件就是当任意方向步长为0, 这时候就只有一种方案.
动态规化+记忆
递归的计算是很多冗余的, 因为很多中间计算在递归下去会被计算多次, 很低效. 这时候我们可以记录一下这些中间结果 这样速度就会快很多(每个 f(x,y) 值只会计算一次)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | $cache = array(); function f($x, $y) { global $cache; if (($x == 0) || ($y == 0)) { return 1; } $key = $x.' '.$y; if (isset($cache[$key])) { // has the result been computed? return $cache[$key]; } $sol = f($x - 1, $y) + f($x, $y - 1); $cache[$key] = $sol; // store the result return $sol; } |
$cache = array(); function f($x, $y) { global $cache; if (($x == 0) || ($y == 0)) { return 1; } $key = $x.' '.$y; if (isset($cache[$key])) { // has the result been computed? return $cache[$key]; } $sol = f($x - 1, $y) + f($x, $y - 1); $cache[$key] = $sol; // store the result return $sol; }
动态规化也不需要用递归来实现, 我们可以用更为高效的数组+迭代的方式, 从低往上计算. 这还不是最优的, 您可以继续优化一下空间复杂度 到O(y).
1 2 3 4 5 6 7 8 9 10 11 | function f($x, $y) { $ans = array(); for ($i = 0; $i <= $x; ++ $i) $ans[$i][0] = 1; for ($i = 0; $i <= $y; ++ $i) $ans[0][$i] = 1; for ($i = 1; $i <= $x; ++ $i) { for ($j = 1; $j <= $y; ++ $j) { $ans[$i][$j] = $ans[$i - 1][$j] + $ans[$i][$j - 1]; } } return $ans[$x][$y]; } |
function f($x, $y) { $ans = array(); for ($i = 0; $i <= $x; ++ $i) $ans[$i][0] = 1; for ($i = 0; $i <= $y; ++ $i) $ans[0][$i] = 1; for ($i = 1; $i <= $x; ++ $i) { for ($j = 1; $j <= $y; ++ $j) { $ans[$i][$j] = $ans[$i - 1][$j] + $ans[$i][$j - 1]; } } return $ans[$x][$y]; }
时间复杂度和空间复杂度都是 O(xy). 为嘛用PHP? 因为PHP是世界上最好的语言.
英文: How Many Ways from A to C via B?
强烈推荐
- 英国代购-畅购英伦
- TopCashBack 返现 (英国购物必备, 积少成多, 我2年来一共得了3000多英镑)
- Quidco 返现 (也是很不错的英国返现网站, 返现率高)
- 注册就送10美元, 免费使用2个月的 DigitalOcean 云主机(性价比超高, 每月只需5美元)
- 注册就送10美元, 免费使用4个月的 Vultr 云主机(性价比超高, 每月只需2.5美元)
- 注册就送10美元, 免费使用2个月的 阿里 云主机(性价比超高, 每月只需4.5美元)
- 注册就送20美元, 免费使用4个月的 Linode 云主机(性价比超高, 每月只需5美元) (折扣码: PodCastInit2022)
- PlusNet 英国光纤(超快, 超划算! 用户名 doctorlai)
- 刷了美国运通信用卡一年得到的积分 换了 485英镑
- 注册就送50英镑 – 英国最便宜最划算的电气提供商
- 能把比特币莱特币变现的银行卡! 不需要手续费就可以把虚拟货币法币兑换
微信公众号: 小赖子的英国生活和资讯 JustYYUK