Decision Trees, Dynamic Programming, and useMemo()
Tags: webdev, reactnative, react, algorithms
Published: 2022-06-26 02:31:34

---
series: Algorithms & Data Structures
---

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5imqeksw3m020zvz8u0o.jpg)
## Table of Contents:
1. The debate over useCallback and useMemo
2. Decision Trees
 - Fibonacci Sequence
3. Dynamic Programming
 - Fibonacci Sequence (notice the repeated work)
 - Principles of DP
 - Another Example, Coin change
 - 5 common problem types – Neetcode (eg. 0/1 Knapsack, unbounded knapsack)
4. useCallback and useMemo
 - A simple example (time saved)
 - How much time does it save in the code?


## 1. The debate over useCallback and useMemo
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/82wujafdm03fzz2jvtkl.png)

1. Basic use of the hooks
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/la3v07fn0vvcqx2mgoy7.png)

2. But you must ensure ALL variables are memo-ed, otherwise React will still re-render the component (read more: [here](https://www.developerway.com/posts/how-to-use-memo-use-callback))
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s9nwgmi3yrvh5nv16idt.png)

3. Memoizing entire components might be more useful
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/w4nwb9jmnojvuge792nv.png)

4. How to profile the useMemo / function to see if it is better
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ri0ie1ugtoxos5yv1o39.png)

### Closing the debate: React Docs for useMemo()
> You may rely on useMemo as a performance optimization, not as a semantic guarantee. In the future, React may choose to “forget” some previously memoized values and recalculate them on next render, e.g. to free memory for offscreen components. Write your code so that it still works without useMemo — and then add it to optimize performance.

This means useMemo does not exactly get "free" memory storage. It has to trade extra memory usage for faster runtimes.

### Computers are so advanced, do all this matter anyway?
**Research Paper**: Why are you so slow? – Misattribution of transmission delay to attributes of the conversation partner at the far-end (https://www.sciencedirect.com/science/article/abs/pii/S1071581914000287)
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s3wpgm4twngzb6713g7q.png)
**Idea**: <u>1.2 seconds delay</u> makes one frustrated with their video-conferencing counterparts.
**Question**: Does useMemo and useCallback really reduce the delay to an extent where users would be less frustrated using the app?
 
## 2. Decision Trees
A [decision tree](https://en.wikipedia.org/wiki/Decision_tree) is a decision support tool that uses a tree-like model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility.

### Fibonacci Sequence
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3r8xn3wtzknz3absphxr.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/q7f4qvio7sy87vbybpwm.gif)

## 3. Dynamic Programming
[Dynamic Programming](https://www.geeksforgeeks.org/dynamic-programming/) is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming. The idea is to simply **store the results of subproblems**, so that we **do not have to re-compute them when needed later**. This simple optimization reduces time complexities from exponential to polynomial.
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/c8kv1jgqtd75yi80wtls.png)
We can see in Fibonacci above that there is repeat work (or subproblems). Let's look at another problem to better our understanding:
* [Coin Change, Medium [Leetcode]](https://leetcode.com/problems/coin-change/)
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nhsrlufqouicsb76okb8.png)

### Thought process explained (see more on Neetcode's youtube tutorial):
1. Brute Force first, try all possible solutions.
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/alknrrhcqky9dwkafvme.png)
2. Need "greedy" algorithm to choose best solution.
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zsvle8j932i63zc3igb2.png)
3. Start with the smallest subproblem that you KNOW FOR SURE. That is, number of coins to make up Amount = 0 is 0!
Hence, Bottom-up DP.
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xup6gnlnbp74pcrszx36.png)

4. Many other articles echo this same procedure for solving Dynamic Programming.
 - https://www.linkedin.com/pulse/master-art-dynamic-programming-ajay-prakash-1d
 - https://www.byte-by-byte.com/fast-method/
 - https://towardsdatascience.com/mastering-dynamic-programming-a627dbdf0229
 - https://leetcode.com/discuss/general-discussion/712010/The-ART-of-Dynamic-Programming-An-Intuitive-Approach%3A-from-Apprentice-to-Master
 
### Work through example? (10 mins)
coins = [1,2,5], amount = 7
```
class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [amount+1] * (amount - 1)
        dp[0] = 0
         
        for a in range(1, amount + 1):
            for c in coins:
                if a - c >= 0:
                    dp[a] = min(dp[a], 1 + dp[a-c])
 
        return dp[amount] if dp[amount] != amount + 1 else -1
```

### Key takeaway
* Rather than computing all subproblems' answers, dp array help to store subproblem answers.
* Dynamic Programming trades MEMORY for RUNTIME

### Other kinds of Dynamic Programming problems ([Neetcode's youtube guide](https://www.youtube.com/watch?v=mBNrRy2_hVs))
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nf9ti4vkjzli9k97f5k8.png)
 
## 4. React Hooks: useMemo() and useCallback()
### Basic Idea
Tutorial: https://www.youtube.com/watch?v=oR8gUi1LfWY
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2kianvh2pjay0jwjhh82.png)

Idea is that after he used the useMemo and useCallback for the Fibonacci number, his text input of "Dave" became much faster and responded after each letter typed. Before it all displayed AFTER the last letter is typed.
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ejydd33h46joes0zx41f.png)

Time saved: about 2 seconds for a BILLION sized array. (maybe it doesn't matter THAT much after all)
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kh68b3bwffv3v0zu32us.png)

### How much time does it save in practical projects?
In practice, most times we memoize small props here and there.
Maybe can memoize entire components?
Or do some profiling to see where it is useful? Because an understanding of the render tree / stack navigator may be useful before deciding when to use useMemo.
### Going Full Circle
**<u>Back to that Question:</u>** Does useMemo and useCallback really reduce the delay to an extent where users would be less frustrated using the app?
- Tradeoffs... tradeoffs... a daily occurrence for an engineer.
- Have to see the context in which these hooks are used.
- While it is still unclear, hopefully at least there is greater awareness about the tradeoffs and principles behind these hooks.