Software Engineer Interview Question – How to Improve Dynamic Progr...

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 能激励我创作更多更好的内容.

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

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

近期热贴 Recent Popular Posts