Search problems

3 problems match “dynamic programming”. Clear

Visitors search a sample. Sign in for free to search every problem. Sign in

1. Edit distance between Big and Bang ●○○○○ 10 ptsGiven two strings $\text{str}_1 = \text{"Big"}$ and $\text{str}_2 = \text{"Bang"}$, find the minimum number of operations needed to convert $\text{str}_1$ into $\text{str}_2$. The allowed operations are deleting a character, replacing a character with another, and inserting a character at any position.
2. Two stock transactions on three days ●○○○○ 10 ptsThe price of a stock on days 1, 2 and 3 is $2, $4 and $1. You may complete at most 2 transactions (a transaction is one buy followed by one sell), and you must sell the stock before you buy again. Find the maximum profit in dollars.
3. Minimum people covering every birthday ●●●●○ 100 ptsAssume a year has 365 equally likely birthdays, each person's birthday is independent of the others, and leap years are ignored. What is the minimum number of people needed so that the probability that every one of the 365 days is someone's birthday is greater than $0.5$?