Dynamic Programming

Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges

Dynamic Programming 的核心在於把大問題拆解成「相互關聯的小問題」來解決，通常小問題可以用遞迴的方式解決、或是迴圈的方式解決

Screen Shot 2022-10-30 at 11.58.09 PM.png

Memoization

通常搭配遞迴解

<aside> 💡

思考方向

  1. 先用一個簡單的例子畫出樹
  2. Bottom up 思考 — 先找出 base case ，當樹遇到 leaf 時要回傳結果
  3. 一路回傳上去就可以知道答案 </aside>

例題：

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1: