How to solve through graph


#1

can someone help me with graph approach , i did’nt get the edit sol


#2

Heyy, Check this out: This uses BFS approach to find the sum. At every iteration, we go through all the possible fib numbers < A.

int Solution::fibsum(int A) {

queue<pair<int,int>> q;

  q.push(make_pair(0,0));

  
  int a=1;
  int b=2;
  int i=0;
  
  vector<int>fib;
  
  fib.push_back(1);
  fib.push_back(2);
for(;i<=A;)
{
    i=a+b;
    a=b;
    b=i;
    fib.push_back(i);      
}
if(fib[fib.size()-1]>A)
fib.pop_back();

int ret=0;

vector<bool> vis(A,false);

while(q.size()!=0)
{

// cout<<(q.front().first)<<" “<<” in "<<q.front().second<<endl;

    if(q.front().first==A)
    {   
        ret=q.front().second;
        break;
    }
    
   for(int i=0;i<fib.size();i++)
    {
        if(vis[fib[i]+q.front().first]==false)
        {
            q.push(make_pair(fib[i]+q.front().first,q.front().second+1));
            vis[fib[i]]=true;
        }
    }
    
    
    
     q.pop();
}

return ret;

}