从A到B再到C有多少种方法?

有这么一题, 一个人从A到C, 一定要经过B, 并且每次走一步向东或者向北, 不能回头, 问一共有多少不同的方法.

travel-from-a-to-b-to-c

暴力搜索(穷举)

理论上说, 你可以用暴力列举所有从A到C的走法然后再一一比较是否经过B, 不过这种方法很低效因为需要列举出所有走法. 如果水平有X步垂直有Y步那么一共的方案有:

$tex_8bd19f28227fa25be0bb077d7ee7a9e4 从A到B再到C有多少种方法? I.T. PHP是最好的语言数学数据结构与算法有意思的面试$ or
$tex_d5f725c0b44d70bdc6ea1d5e3add755d 从A到B再到C有多少种方法? I.T. PHP是最好的语言数学数据结构与算法有意思的面试$

可以这么理解, 一共有 x+y 步选其中 x 或者 y 步来往东或者往北走.

纯数学方法: 排列组合

细想一下, 我们只要分两个阶段即可: 第一个阶段计算由A到B的方法数, 第二个阶段计算由B到C的方法数, 然后这么一乘就是最后的方案数了.

$tex_08d0d996cdb4c348af7e1f435eff9a0e 从A到B再到C有多少种方法? I.T. PHP是最好的语言数学数据结构与算法有意思的面试$ .

根据本题, 最终方案为 $tex_70db27f2498262158da715c5e03965c4 从A到B再到C有多少种方法? I.T. PHP是最好的语言数学数据结构与算法有意思的面试$ 和 $tex_5adb5f7307dff7e63a9f9fd389030898 从A到B再到C有多少种方法? I.T. PHP是最好的语言数学数据结构与算法有意思的面试$ 最终结果是 8820.

递归

假设我们定义了 f(x, y) 用于计算水平x步, 垂直y步的方案数: 那么:

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) 值只会计算一次)

$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).

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?

GD Star Rating
loading...

本文一共 470 个汉字, 你数一下对不对.

从A到B再到C有多少种方法?. (AMP 移动加速版本)
上一篇: 软件工程师面试技巧之动态规化 - 整数拆分
下一篇: 进一步改进动态规化的空间复杂度

赞赏我的几个理由.

¥ 打赏支持

扫描二维码，分享本文到微信朋友圈

小赖子的英国生活和资讯

从A到B再到C有多少种方法?

暴力搜索(穷举)

纯数学方法: 排列组合

递归

动态规化+记忆

2 条评论

评论

暴力搜索(穷举)

纯数学方法: 排列组合

递归

动态规化+记忆

相关文章：

2 条评论

评论