Min Steps to Convert x to y (Recursion, BFS, DP)

You want to transform a natural number x into y. You can use the following operations:

Add n to x
Multiply x by 2
Multiply x by 3

Given the natural numbers x, y, and n as parameters, complete the function solution to return the minimum number of operations required to transform x into y.
If it's impossible to transform x into y using these operations, return -1.

Solution 1 - Recursion

I tried to solve this problem using recursion first time however it was not efficient way to solve this problem in terms of time complexity.
it failed to pass the test case with large numbers.

function solution(x, y, n) {
  let result = Infinity;
 
  function go(cur, step) {
    if (cur === y) {
      result = Math.min(result, step);
      return;
    }
 
    if (cur > y) return;
 
    go(cur + n, step + 1);
    go(cur * 2, step + 1);
    go(cur * 3, step + 1);
  }
 
  go(x, 0);
 
  return result === Infinity ? -1 : result;
}

Solution 2 - BFS

Next solution is using BFS.
Since BFS finds the shortest path from the start node to the end node, it is a better solution than recursion in terms of time complexity.
Additionally, we can use a set to store visited nodes to avoid infinite loops.

function solution(x, y, n) {
  const visited = new Set();
  const queue = [[y, 0]];
 
  while (queue.length) {
    const [cur, count] = queue.shift();
    if (cur === x) return count;
    if (visited.has(cur)) continue;
    visited.add(cur);
 
    if (cur - n >= x) queue.push([cur - n, count + 1]);
    if (cur % 2 === 0 && cur / 2 >= x) queue.push([cur / 2, count + 1]);
    if (cur % 3 === 0 && cur / 3 >= x) queue.push([cur / 3, count + 1]);
  }
 
  return -1;
}

Solution 3 - DP (Most Efficient)

The most efficient solution is using DP.
We can solve this problem by using DP with the following steps:

function solution(x, y, n) {
  const dp = new Array(y + 1).fill(Infinity);
  dp[x] = 0;
  for (let i = x; i <= y; i++) {
    dp[i + n] = Math.min(dp[i + n], dp[i] + 1);
    dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);
    dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1);
  }
  return dp[y] !== Infinity ? dp[y] : -1;
}