# Dynamic Programming Review
## Dynamic Programming and NP-hardness
1) Prove that Knapsack problem is NP-hard
2) What is the implication?

[Solution Link](https://www.quora.com/How-can-one-prove-the-knapsack-problem-is-NP-complete)

## Dynamic Programming and Combinatorics
Given that we have thrown a coin $n$ times, how many arrangements are there that do not have three consecutive tails?

[Solution Link](https://medium.com/@harryjobz/coin-problem-lets-code-2-0-83b607bdcfdc)

## Dynamic Programming and Probability (random Walk on a graph)
Given a graph $G = (V,E)$, we start from vertex $x$. Besides, we know that after one time step, the probability that we go from vertex $u$ to $v$ has probability $p_{u,v}$. Compute the probabilities that after $k$ time step, we end up at vertex $y$.

## Dynamic Programming and randomness and game
A gambler has $x, she is allowed to play a game of chance k times and her goal is to maximize her probability of ending up with a least $p. If the gambler bets $b on a play of the game, then with probability 0.4 she wins the game and earn additional $b; with probability 0.6, she loses the bet amount $b. What is the maximal probability that she could win the game?
[Solution Link](https://en.wikipedia.org/wiki/Stochastic_dynamic_programming)