optimistiks

export function findTribonacci(n) {
  // we use an array of fixed size so we keep a constant amount of subproblem solutions at each iteration
  // therefore ensuring constant space complexity
  const dp = [0, 1, 1];

  if (n < 3) {
    return dp[n];
  }

  for (let i = 3; i <= n; ++i) {

optimistiks

export function canPartitionArray(nums) {
  // find sum of items
  const total = nums.reduce((acc, num) => acc + num, 0);

  // if there is a remainder, it's not possible to split the array in two subsets with the same sum
  if (total % 2 !== 0) {
    return false;
  }

  // get our half sum, we need to determine if there is a subset that sums up to half sum,

optimistiks

function countingBits(n) {
  const dp = [0, 1];

  // even numbers have their 1s count equal to count of the number / 2
  // odd numbers have their 1s count equal to count of the number / 2, plus one
  // for example, binary representation of 7 is 111 (count = 3)
  // first we get count of 3 (floor(7 / 2)) which equals to 2 (binary = 11), and then plus one
  // binary representation of 4 is 100 (count = 1)
  // same as count of 2 (4/2), which is 1

optimistiks

function updateMatrix(mat) {
  // first iteration, from top left to bottom right
  // calculate min distance of cell i,j as min distance of it's left and top neighbors + 1
  // if left / top is inaccessible, use Infinity
  for (let i = 0; i < mat.length; ++i) {
    for (let j = 0; j < mat[i].length; ++j) {
      if (mat[i][j] === 0) {
        continue;
      }
      mat[i][j] =

optimistiks

function houseRobber(money) {
  return Math.max(
    calcMax(money, 0, money.length - 1),
    calcMax(money, 1, money.length)
  );
}

function calcMax(money, from, to) {
  const dp = [];
  for (let i = from; i < to; ++i) {

optimistiks

export function maxProduct(nums) {
  if (nums.length === 0) {
    return 0;
  }

  // we are going to track the minimum value as well as we progress
  // because we might encounter a negative value, and then another negative value
  // so it's possible our minimal value will be flipped to be a positive, and a new maximum

  // store here the max seen product so far

optimistiks

function combinationSum(nums, target) {
    // prepare a dp array
    // indexes are target values up to target
    // for example dp [3] contains all unique combinations that add up to 3
    // so at the end we will be able to return dp[target]
    const dp = Array(target + 1).fill().map(() => []);
    // the only combination that sums up to 0 is an empty combination
    dp[0] = [[]]
    // start iterating target values, from 1 to target including
    for (let subTar = 1; subTar <= target; ++subTar) {

optimistiks

function wordBreak(s, wordDict) {
  // we initialize the dp array of length s.length + 1
  // dp[i] answers the question, whether or not the string up to but not including s[i] can be broken up to words
  // so dp[s.length] will answer the initial question of whether or not the whole string can be broken up to words
  const dp = Array(s.length + 1).fill(false);
  // dp[0] is true because string up to but not inclusing s[0] is an empty string so we consider it a valid word
  dp[0] = true;
  // start iteration from the second character
  for (let i = 1; i <= s.length; ++i) {
    // inner loop starts from the first character, up to i

optimistiks

function countPalindromicSubstrings(s) {
  // d[i][j] answers the question: is substring [i, j) a palindrome?
  const dp = Array(s.length + 1)
    .fill()
    .map(() => Array(s.length + 1).fill(false));
  // so if the word is lever
  // dp[0][5] is the answer (which means size dp size is s.length + 1 x s.length + 1)

  // since every single char is a palindrome, prefill solutions to those subproblems
  // in word "cat", "a" is substring [1, 2)

optimistiks

function longestCommonSubsequence(str1, str2) {
  // prepare array m*n for top down memoization
  const dp = Array(str1.length).fill().map(() => Array(str2.length).fill(null))
  return rec(0, 0, str1, str2, dp)
}

function rec(i1, i2, str1, str2, dp) {
  if (i1 >= str1.length || i2 >= str2.length) {
    return 0
  }