Software Engineer Interview Question – How to Improve Dynamic Programming Space Complexity? 进一步改进动态规化的空间复杂度

in cn •  7 years ago  (edited)

In yesterday's post, we present the final ‘optimized’ solution using Dynamic Programming, which is implemented using a 2 dimensional array with iteration. Let’s review this code: 

昨天发了这个帖子讲到动态规化的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];

}

 We know that the time complexity is O(xy) and the space complexity is also O(xy) where a 2-D array is allocated. So, can we do better? If we take a look at the core iteration of this Dynamic Programming (DP) algorithm: 

 $ans[$i][$j] = $ans[$i - 1][$j] + $ans[$i][$j - 1];

 We can see that in order to compute ans[i][j] we need to know ans[i – 1][j] and ans[i][j – 1]. So, we can visualize this as: we need the result of its previous row only i.e. we don’t need to know ans[i – 2][*] when we compute ans[i][*]. Therefore, we can compress the 2-D array into 1-D array, where we store the intermediate results of ans[i – 1] only. The space complexity is thus improved to O(y). With this modification, the loop sequence becomes important, you need to loop from the smaller index and the inner loop should be exactly from 1 to y, which accumulates the intermediate results. 

 这个时间复杂度是 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];

}

 We initialize the array with answer 1’s which means ans[0][*] = 1 (with x = 0), by doing this, we also get rid of O(y) loop. This is the shortest, fastest and cleanest solution to this puzzle, as I believe :) 

 这么一修改 循环的顺序就变得格外的重要了, 因为内循环我们必须严格从1到 y 来累计中间结果. 这样一优化, 时间空间复杂度都达到最优了, 而且代码运行速度也最快了(就动规这个算法来讲), 代码也更简洁了. 

 Originally published at https://steemit.com Thank you for reading my post, feel free to FOLLOW and Upvote @justyy which motivates me to create more quality posts.

原创首发于 https://steemit.com 非常感谢阅读, 欢迎FOLLOW和Upvote @justyy  能激励我创作更多更好的内容.    

 // 同步到我的中文博客英文算法博客  

近期热贴 Recent Popular Posts 

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  

wow !!! It really helps !!!
Thanks

  ·  7 years ago 

Please could you re-steeeeeem if it helps? :)

#NICE Question
#Post On Github and Stackoverflow

  ·  7 years ago 

Thanks...

Done
Followed & Upvoted

  ·  7 years ago 

Thank you!

This post received a 3.8% upvote from @randowhale thanks to @justyy! For more information, click here!

  ·  7 years ago 

1 SBD for around 1.5 SBD.. is this what you can do?

isn't there better ways to calculate a position in pascals triangle? i'm thinking n=x+y , r=y. return n!/r!(n-r)! (though my translation might be need fixing...haven't done anything like it in 2 decades)

  ·  7 years ago 

囧 天书

  ·  7 years ago 

有么?

对我来说 是的:)

太強了,不斷優化這個小小的程式,早前看到你上一個帖文還以為已經是最佳方法了,哈哈

我只能先点赞再慢慢看,我消化能力有限