iJustErikk

const howSum = (targetSum, numbers, memo = new Map()) => {
    const key = `${targetSum}`;
    if (memo.has(key)) return memo.get(key);
    if (targetSum === 0) return [];
    if (targetSum <= 0) return null;
    for (let num of numbers) {
        const remainder = targetSum - num;
        const res = howSum(remainder, numbers, memo);
        if (res === null) continue;
        res.push(num);

iJustErikk

// finds what combination of nums in numbers generates targetsum
const howSum = (targetSum, numbers) => {
    if (targetSum === 0) return [];
    if (targetSum <= 0) return null;
    for (let num of numbers) {
        const remainder = targetSum - num;
        const res = howSum(remainder, numbers);
        if (res === null) continue;
        res.push(num);
        return res;

iJustErikk

// t/f
// use number from numbers as many times as needed to construct targetSum
const canSum = (targetSum, numbers, memo = new Map()) => {
  const key = `${targetSum}`;
  if (targetSum === 0) return true;
  if (memo.has(key)) return memo.get(key);
  for (let currentNum of numbers) {
    const after = targetSum - currentNum;
    if (after < 0) continue;

iJustErikk

// t/f
// use number from numbers as many times as needed to construct targetSum
const canSum = (targetSum, numbers) => {
  if (targetSum === 0) return true;
  for(let i = 0; i < numbers.length; i += 1) {
    const currentNum = numbers[i];
    const after = targetSum - currentNum;
    if (after < 0) continue;
    if(canSum(after, numbers)) return true;
  }

iJustErikk

const gridTraveler = (x, y, z, memo = new Map()) => {
  const key = `${x},${y},${z}`;
  if (memo.has(key)) return memo.get(key);
  if (x === 0 || y === 0 || z === 0) return 0;
  if (x === 1 && y === 1 && z === 1) return 1;
  memo.set(key, gridTraveler(x - 1, y, z, memo) + gridTraveler(x, y - 1, z, memo)) + gridTraveler(x, y, z - 1, memo));
  return memo.get(key);
};
console.log(gridTraveler(10, 10, 10));

iJustErikk

const gridTraveler = (m, n, memo = new Map()) => {
  const key = `${m},${n}`;
  if (memo.has(key)) return memo.get(key);
  if (m === 0 || n === 0) return 0;
  if (m === 1 && n === 1) return 1;
  memo.set(key, gridTraveler(m - 1, n, memo) + gridTraveler(m, n - 1, memo));
  return memo.get(key);
};
console.log(gridTraveler(20, 20));

iJustErikk

const spaceTraveler = (x, y, z) => {
  if (x === 0 || y === 0 || z === 0) return 0;
  if (x === 1 && y === 1 && z === 1) return 1;
  return spaceTraveler(x - 1, y, z) + spaceTraveler(x, y - 1, z) + spaceTraveler(x, y, z - 1);
};
console.log(gridTraveler(4, 4, 4));
// you are traveling in space
// you are at (0, 0, 0)
// find how many ways you can get to (x, y, z) by only increasing to them
// x,y,z > 0, are integers

iJustErikk

const gridTraveler = (m, n) => {
  if (m === 0 || n === 0) return 0;
  if (m === 1 && n === 1) return 1;
  return gridTraveler(m - 1, n) + gridTraveler(m, n - 1);
};
console.log(gridTraveler(15, 15));

iJustErikk

// map supports has(key), get(key) and set(key, val)
const fib = (n, memo = new Map()) => {
  if (memo.has(n)) return memo.get(n);
  if (n <= 1) return 1;
  memo.set(n, fib(n-1, memo) + fib(n-2, memo));
  return memo.get(n);
};
for(let i = 0; i <= 1476; i++) {
  console.log(i, fib(i));
}

iJustErikk

def naive_fibbo(n):
  if (n <= 2): return 1
  return naive_fibbo(n-1) + naive_fibbo(n-2)