Find a sum using just two different digits The problem statement was pretty easy and I was able to run half of the test cases, but some of the test cases in the end gave me the error of memory limit reached. What can I do here to improve the memory efficiency of my code?
Question: Find the min number of &quot;usable&quot; integers required to reach the N. The &quot;usable integers&quot; are those that contain only 4 or 5 in their decimal representation, e.g. 4,5,455,545454.
So to reach 9, answer would be 2 (4+5) My approach: Creating a vector consisting of all usable numbers up to N and using dynamic programming solution on that vector to find the minimum number of elements required to reach N.
My code:
int getCount(int N) {
    vector&lt;int&gt; vec;vec.push_back(4);vec.push_back(5);
    int i = 0;int temp = 0; 
    while(true) {
        temp = vec[i] * 10 + 4;
        if(temp &gt; N)
            break;
        vec.push_back(temp);
        temp = vec[i] * 10 + 5;
        if(temp &gt; N)
            break;
        vec.push_back(temp);
        i++;
    }
    
    return getCountDP(vec,vec.size(),N);
}

int getCountDP(vector&lt;int&gt; vec,int size, int N){  

    int dp[size+1][N+1];

    for(int i = 0 ; i &lt;= N; i++) {
        dp[0][i] = INT_MAX - 1;
    }
    
    for(int i = 0 ; i &lt; size+1; i++) {
        dp[i][0] = 0;
    }

    for (int i = 1; i &lt;= size; i++) { 
        for (int j = 1; j &lt;= N; j++) { 
            if (vec[i - 1] &gt; j) { 
                dp[i][j]= dp[i-1][j]; 
            } 
            else { 
                dp[i][j]= min(dp[i-1][j],dp[i][j-vec[i-1]]+1); 
            } 
        } 
    } 
    return dp[size][N]; 
}
Since your question is about Memory Limit Exceed. And the most memory consumed item is dp. You are going to make your dp matrix smaller. Your current memory usage is \$O(2^{log_{10}n}\cdot n) = O(n^2)\$. And you need to reduce it to \$O(n)\$.
Let's write down your current dp function:
$$ dp_{i,j} = \min \{ dp_{i-1,j}, dp_{i, j-usable_i}+1 \} $$
First, consider you only need dp[i] and dp[i-1] during iteration. All previous rows are not necessarily any more. You may only declare two rows as dp1[N + 1] and dp2[N + 1]. (To make the logic for even and odd rows consistent, use two pointers point to these array.) By using this approach, memory usage may reduced into \$O(2n) = O(n)\$.
Another approach may be just reduce your dp function into 1 dimension:
$$ dp_{j} = \min_{n \in usable} \{dp_{j-n}\} + 1 $$
So, you may only maintain dp[N + 1] instead. This also cost \$O(n)\$ memory. The second approach also make the array reusable when this function is invoked later. If you are going to handle multiple testcases in one run. You may simply declare it as global variable dp[MAX_N + 1] to reduce its time consume.
#include &lt;stdio.h&gt;

const int MAX_N = 1000000;
const int MAX_VAL = 128; // 2 ^ (log10(MAX_N) + 1)

int getCount(int n) {
  static int filled = 0;
  // values hold all numbers only contais 4 or 5 in 0 ~ 1e6
  static int values[MAX_VAL] = {4, 5};
  // steps is the array for dp
  // steps[i] = min(steps[i - values[j]] + 1 for every j)
  static int steps[MAX_N];
  int i, j, step, min_step;
  if (n &gt; MAX_N) return -1; // We do not support input &gt; 1e6
  // When first time run, we fill all values
  if (filled == 0) {
    for (i = 2, j = 0; i &lt; MAX_VAL; j++) {
      values[i++] = values[j] * 10 + 4;
      values[i++] = values[j] * 10 + 5;
    }
    steps[0] = 0;
    filled = 1;
  }
  for (i = filled &gt; 1 ? filled : 1; i &lt;= n; i++) {
    // We use MAX_N+1 for values cannot be reached
    min_step = MAX_N + 1;
    for (j = 0; values[j] &lt;= i; j++) {
      step = steps[i - values[j]] + 1;
      if (step &lt; min_step) min_step = step;
    }
    steps[i] = min_step;
  }
  filled = n;
  if (steps[n] &gt; n) return -1;
  return steps[n];
}

int main() {
  int n;
  for (n = 0; n &lt; MAX_N; n++) {
    printf(&quot;%d\n&quot;, getCount(n));
  }
}