JSFiddle - React, Tailwind, and code Playground

by Eugen Sunic

JavaScript

function helper(A, i, j, dp) {

  // Base Case 
  if (i == A.length) {
    return 0;
  }

  // To avoid solving overlapping subproblem
  if (dp[i][j] != -1) {
    console.log(i, j)
    return dp[i][j];
  }

  // Add current to the minimum  of the next paths
  // and store it in dp matrix
  const a = A[i][j] + Math.min(helper(A, i + 1, j, dp), helper(A, i + 1, j + 1, dp));
  console.log('a', a, i,j);
  return dp[i][j] = a;


}


function minSumPath(A) {
  let n = A.length;

  // Initializating of dp matrix
  let dp = new Array(n);
  for (let i = 0; i < n; i++) {
    dp[i] = new Array(n).fill(-1);
  }
  // calling helper function
  return helper(A, 0, 0, dp);
}

console.log(minSumPath([
  [2],
  [3, 9],
  [1, 6, 7]
]))