0

background

When I was solving a dynamic programming problem in leetcode, I used a statement like dp[m][n]={0} to initialize the array but sometimes it failed to set the array to all zeros which led to the wrong answer.

solution

However, after I changed the code to memset(dp,0,sizeof(dp)), the dp array was initialized successfully.

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
         int m  = obstacleGrid.size();
         int n = obstacleGrid[0].size();
         unsigned long dp[m][n];// 
         //unsigned long dp[m][n] = {0}; // failed when printed out
         memset(dp,0,sizeof(dp)); // success

         //....
}
}

my question

I was thinking that the issue was due to that the array size is dynamical. That means the way I initialized the 2d dynamic array is wrong. Should use pointer or vector to initialize such dynamic-size 2d array.

But what bothered me is that from another point of view, 2d array was a local variable which stored in the stack. That means the space it used will be free when the function return. In this way, each time the 2d array will get some brand new space with all zeros using dp[m][n] ={0}. Unfortunately, the result proved I was wrong and I have to use memset() to ensure array was intialized all zeros. So I wonder someone could give me some help on this C++ thing.

TizeeU0U
  • 474
  • 3
  • 8
  • 5
    `unsigned long dp[m][n];` is not legal in standard `c++` because by the rules of the standard `n` and `m` must be compile time constants: https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard My advice is to never use `VLAs` in `c++` instead use `std::vector`. – drescherjm Jul 05 '19 at 17:11
  • ...unless `m` and `n` are `constexpr` (and in OP's example they are not). – Evg Jul 05 '19 at 17:12
  • @Evg I don't think it fits. OP already tried `unsigned long dp[m][n] = {0}`, it didn't work. – HolyBlackCat Jul 05 '19 at 17:12
  • Also depending on the size of `n` and `m` you could easily have a stack overflow. – drescherjm Jul 05 '19 at 17:18
  • 1
    Besides that, you're already using `vector>` elsewhere. So why didn't you simply follow that pattern and use `std::vector> dp(m, std::vector(n))`? – PaulMcKenzie Jul 05 '19 at 18:03
  • Thanks for helping. The rules seem like C's. I used the c array for the sake of time and memory efficiency as the vector in C++ is a wrapper class of an array which has some built-in functions that never be used. In this problem, I just use an array to store data. In competitive programming, the coding style is very different, I may have to make a choice between the safety and the efficiency. – TizeeU0U Jul 06 '19 at 04:31

0 Answers0