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

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?
• 进一步改进动态规化的空间复杂度
• How many ways from A to C via B?
• 从A到B再到C有多少种方法? 

近期热贴 Recent Popular Posts 

•  第一次打肿脸充胖子 - 花了200STEEM租1万SP四周！  
• 24 Poker Game 24点扑克游戏
• Software Engineer Interview Question - Dynamic Programming - Integer Break 软件工程师面试技巧之 动态规化 - 整数拆分
• How to Claim BCC? BTC Hard-Fork via C program (Linux) 小白教程: 怎么领取 BCC (Bitcoin Cash) ? 
• I wrote a Chinese Chess Program 软件分享: 智慧中国象棋 (Chinese Chess)
• Planning Cards – Agile Poker Game! 敏捷开发扑克游戏
• Software Engineer Interview Question - How to Check Valid Sudoku in C/C++? 软件工程师面试技巧之 如何检查数独的有效性
• Google Interview Question – Print Message - 去年 Google 的面试题 - 打印消息 
• Software Engineer Interview Tips - Using Hashtable to Reduce Runtime Complexity 软件工程师面试技巧之 使用哈希表降复杂度 
• Technology-driven or Business-model-driven? 技术优先还是商业模式优先 – 献给在30多岁还在写代码的朋友们 
• 记录那些值得回忆的精彩瞬间