Minimum (Maximum) Path to Reach a Target

Choose minimum / maximum path among all possible paths before the current state, then add value for the current state.

dfs[i] = min( dfs[i-1], dfs[i-2], ... , dfs[i-k] ) + cost[i]

🟡  Coin Change

<aside> 💡 DFS, iterate on coins and fill in ways with 0 if target amount reached and Infinity if it’s over. Return smallest of ways + 1 to parent indicating that a coin was taken.

</aside>

https://leetcode.com/problems/coin-change/

function coinChange(coins, amount) {

  function dfs(remaining) {
    if (remaining === 0) return 0;
    if (remaining < 0) return Infinity;

    const ways = [];

    for (let coin of coins) {
      const way = dfs(remaining - coin);
      ways.push(way);
    }

    return 1 + Math.min(...ways);
  }

  const result = dfs(amount);

  return result === Infinity ? -1 : result;
}

• Recursion tree
• Intuition
• Memoization

Distinct Ways

Sum all possible ways.

dfs[i] = dfs[i-1] + dfs[i-2], ... , + dfs[i-k]