Software Engineer Interview Question – How to Improve Dynamic Programming Space Complexity?

In this 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:

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];
}

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:

1

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

$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.

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];
}

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 🙂

You may also like: 进一步改进动态规化的空间复杂度

–EOF (The Ultimate Computing & Technology Blog) —