昨天发了这个帖子讲到动态规化的2种改进, 一种是记忆, 另一种是把递归改成迭代. 今天稍微想了一下, 还可以从空间复杂度里入手. 我们先看一下之前的’最优’方案:
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) 而空间复杂度是 O(xy), 我们需要定义一个二维数组, 可是你看, 我们在算 ans[i][j] 的时候只用到了 ans[i] 和 ans[i – 1] 行的两个值, 也就是说我们并不需要用到 ans[i – 2], ans[i – 3] .. 更早的值, 所以我们完全可以用一维数组来保存上一行的值, 这样的话只需要 O(y) 数组就可以了.
1 2 3 4 5 6 7 8 9 10 | function work($x, $y) { $ans = array(); for ($i = 0; $i <= $y; ++ $i) $ans[$i] = 1; for ($i = 1; $i <= $x; ++ $i) { for ($j = 1; $j <= $y ; ++ $j) { $ans[$j] += $ans[$j - 1]; } } return $ans[$y]; } |
function work($x, $y) { $ans = array(); for ($i = 0; $i <= $y; ++ $i) $ans[$i] = 1; for ($i = 1; $i <= $x; ++ $i) { for ($j = 1; $j <= $y ; ++ $j) { $ans[$j] += $ans[$j - 1]; } } return $ans[$y]; }
这么一修改 循环的顺序就变得格外的重要了, 因为内循环我们必须严格从1到 y 来累计中间结果. 这样一优化, 时间空间复杂度都达到最优了, 而且代码运行速度也最快了(就动规这个算法来讲), 代码也更简洁了.
英文: Software Engineer Interview Question – How to Improve Dynamic Programming Space Complexity?
强烈推荐
- 英国代购-畅购英伦
- 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