# Dynamic programming

## What is Dynamic Programming?

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.

## [Leetcode 198] House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

1 | Input: nums = [1,2,3,1] |

Example 2:

1 | Input: nums = [2,7,9,3,1] |

Constraints:

- 1 <= nums.length <= 100
- 0 <= nums[i] <= 400

Solution:

1 | class Solution: |

## [Leetcode 746] Min Cost Climbing Stairs

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:

1 | Input: cost = [10,15,20] |

Example 2:

1 | Input: cost = [1,100,1,1,1,100,1,1,100,1] |

Constraints:

- 2 <= cost.length <= 1000
- 0 <= cost[i] <= 999

Solution:

1 | class Solution: |

## [Leetcode 790] Domino and Tromino Tiling

You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.

Given an integer n, return the number of ways to tile an 2 x n board. Since the answer may be very large, return it modulo 109 + 7.

In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.

Example 1:

1 | Input: n = 3 |

Example 2:

1 | Input: n = 1 |

Constraints:

- 1 <= n <= 1000

Solution:

1 | class Solution: |

## [Leetcode 1137] N-th Tribonacci Number

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

Example 1:

1 | Input: n = 4 |

Example 2:

1 | Input: n = 25 |

Constraints:

- 0 <= n <= 37
- The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

Solution:

1 | class Solution: |