Summary - Dynamic Programming

Nth Fibonacci Number

Problem: Find the Nth Fibonacci number.

Recursive Approach: Uses repeated calculations.

Memoization:

Use an array DP to store intermediate results.

Time complexity: O(N), Space complexity: O(N).

Tabulation:

Use an iterative method with a bottom-up approach.

Time and space complexity: O(N).

Maximum Sum of Non-Adjacent Elements

Problem: Find the highest sum of non-adjacent elements.

Recursive Approach: "Pick or not pick" strategy.

Memoization:

Use an array DP for subproblems.

Time complexity: O(N), Space complexity: O(N).

Tabulation:

Use a bottom-up approach with an iterative method.

Time and space complexity: O(N).

Ninja's Training Schedule

Problem: Maximize merit points over N days with constraints on consecutive activities.

Recursive Approach: Track activities for each day.

Memoization:

Use a 2D array dp to store results.

Time complexity: O(N×4), Space complexity: O(N×4).

Tabulation:

Use nested loops to fill the dp array.

Time and space complexity: O(N×4).

Grid Unique Paths

Problem: Find all unique paths in an MxN grid.

Recursive Approach: Move right and down.

Memoization:

Use a 2D array dp for subproblems.

Time and space complexity: O(M×N).

Tabulation:

Use nested loops to fill the dp array.

Time and space complexity: O(M×N).

Zero One Knapsack

Problem: Maximize the total value within a weight limit W.

Recursive Approach: "Pick or not pick" strategy.

Memoization:

Use a 2D array dp for subproblems.

Time complexity: O(N×W), Space complexity: O(N×W).

Tabulation:

Use nested loops to fill the dp array.

Time and space complexity: O(N×W).

For more detailed information, refer to the Notion link:

Dynamic Programming⁠

⁠

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.