进一步改进动态规化的空间复杂度

昨天发了这个帖子讲到动态规化的2种改进, 一种是记忆, 另一种是把递归改成迭代. 今天稍微想了一下, 还可以从空间复杂度里入手. 我们先看一下之前的’最优’方案:

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) 数组就可以了.

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?

GD Star Rating
loading...

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

进一步改进动态规化的空间复杂度. (AMP 移动加速版本)
上一篇: 从A到B再到C有多少种方法?
下一篇: 英国慢节奏的村庄生活 - 每日散步村口溜娃

赞赏我的几个理由.

¥ 打赏支持

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

小赖子的英国生活和资讯

进一步改进动态规化的空间复杂度

评论

相关文章：

评论