<jupyter_start><jupyter_text>![fibonacci_tree.png](img/fibonacci_tree.png)<jupyter_code>Here in the above tree:
    --> f4 is called 2 times
    --> f3 is called 3 times
    --> f2 is called 5 times
    
DP uses a storage so that you do not call on the same sub problem again and again

Every recursive problem is not an overlapping subproblem. For example, factorial of a number

Fact(5) --> Fact(4) --> Fact(3) --> Fact(2) --> Fact(1) --> Fact(0) 

Recursion will always have optimal substructure but DP is applied where it also has overlapping sub problem<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09693877551020408, 'fraction_numerical': 0.02040816326530612, 'mean_word_length': 3.75, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '376558', 'license': 'Unlicense', 'n_tokens_mistral': 198, 'n_tokens_neox': 180, 'n_words': 75, 'path': '24 DP-1/24.01 Intro to DP.ipynb', 'repo_name': 'suhassuhas/Coding-Ninjas---Data-Structures-and-Algorithms-in-Python', 'size': '588'}