Tag: 面试题

昨天发了这个帖子讲到动态规化的2种改进, 一种是记忆, 另一种是把递归改成迭代. 今天稍微想了一下, 还可以从空间复杂度里入手. 我们先看一下之前的’最优’方案: function f($x, $y) { $ans = array(); for ($i = 0; $i <= $x; ++ $i) $ans = 1; for ($i = 0; …

有这么一题, 一个人从A到C, 一定要经过B, 并且每次走一步向东或者向北, 不能回头, 问一共有多少不同的方法. 暴力搜索(穷举) 理论上说, 你可以用暴力列举所有从A到C的走法 然后再一一比较是否经过B, 不过这种方法很低效因为需要列举出所有走法. 如果水平有X步垂直有Y步那么一共的方案有: or 可以这么理解, 一共有 x+y 步 选其中 x 或者 y 步来往东或者往北走. 纯数学方法: 排列组合 细想一下, 我们只要分两个阶段即可: 第一个阶段计算由A到B的方法数, 第二个阶段计算由B到C的方法数, 然后这么一乘就是最后的方案数了. …