With this code I was trying to calculate unique ways to reach a certain sum by adding array elements with a dynamic programming approach, the program works correctly but takes more time than expected so I checked if it is storing calculated values in the my vector, but it not storing any values at all.

#include <iostream>
#include <vector>
using namespace std;
// recursive function to include/excluded every element in the sum.
long long solve(int N,int sum, int* coins, long long mysum, vector<vector<long long >> &my, long long j){

      if (mysum == sum){
          return 1;

      }if (mysum>sum){
          return 0;
      }
      if (my[mysum][j]!=-1){
          return my[mysum][j];
      }

      long long ways = 0;
      while (j<N){
          ways = solve (N,sum,coins,mysum coins[j],my, j);
          j  ;
      }
       //Line in question 
      return my[mysum][j] = ways;
  }
    int main() {

        // code here.
        int N=3;
        int coins[] = {1,2,3};
        int sum =4;
        int check =  INT_MIN;
        vector<vector<long long int>> my(sum 1,vector<long long int>(N 1,-1));
        cout<< solve (N,sum,coins,0,my,0)<< " ";

        // traversing to check if the memoizing vector stored the return values
        for (int x=0; x<sum 1; x  ){
            for (int y=0; y<N; y  ){
                if (my[x][y]!=-1){
                    check = 0;
                }
            }
        }
        cout<< check;
        return 0;
    }

output: 4 -2147483648

CodePudding user response：

It does store the values, your checking code is not correct.

Try this version in your check

    for (int y=0; y<N 1; y  ){ // N 1 not N

CodePudding user response：

So, the problem is that j is incrementing because of the for loop. The function fills my[newsum][j] only after the for loop's scope is over. By that time j==N and only my[newsum][N] is filled, the preceding values of j are left empty. This can be solved by make another variable equal to j that isn't increamented.