5 posts tagged with "dp"

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  if (numRows === 1) {
    return [[1]];
  }

  if (numRows === 2) {
    return [[1], [1, 1]];
  }

  let rows = [[1], [1, 1]];

  for (let i = 2; i < numRows; i++) {
    let prevRow = rows[i - 1];

    let currentRow = [1];
    for (let j = 0; j < prevRow.length - 1; j++) {
      currentRow.push(prevRow[j] + prevRow[j + 1]);
    }
    currentRow.push(1);

    rows.push(currentRow);
  }
  return rows;
};

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function (rowIndex) {
  if (rowIndex === 0) {
    return [1];
  }

  if (rowIndex === 1) {
    return [1, 1];
  }

  let rows = [[1], [1, 1]];

  for (let i = 2; i <= rowIndex; i++) {
    let prevRow = rows[i - 1];

    let currentRow = [1];

    for (let j = 0; j < prevRow.length - 1; j++) {
      currentRow.push(prevRow[j] + prevRow[j + 1]);
    }
    currentRow.push(1);

    rows.push(currentRow);
  }

  return rows[rowIndex];
};

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function (prices) {
  let based = prices[0];
  let result = 0;

  for (let i = 1; i < prices.length; i++) {
    let diff = prices[i] - based;

    if (diff < result) {
      if (diff < 0) {
        based = prices[i];
      }
    } else {
      result = diff;
    }
  }

  return result;
};

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function (s, t) {
  let k = 0;

  for (let i = 0; i < t.length; i++) {
    if (s[k] === t[i]) {
      k++;
    }
  }

  return k === s.length;
};

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
  if (n === 1) {
    return 1;
  }

  const cache = {
    0: 1,
    1: 1,
  };

  for (let i = 2; i <= n; i++) {
    cache[i] = cache[i - 1] + cache[i - 2];
  }

  return cache[n];
};