**1. Climbing Stairs **

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Write a recursive dynamic programming algorithm (not iterative) in Stairs.java that will run in O(n) time.

**Because of the integer overflow problem your solution only needs to be correct up to Stairs 30.**

Test Cases:

$java Stairs 3 3 $java Stairs 4 5 $java Stairs 10 89 $java Stairs 20 10946 $java Stairs 30 1346269 $java Stairs 400~~1075736893~~//incorrect due to Integer overflow. 284812298108489611757988937681460995615380088782304890986477195645969271404032323901 //correct using BigInteger

**2. Best Time to Buy and Sell Stock**

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit. Implement your solution using dynamic programming to be O(n) in the file Stock.java.

Test Cases:

$java Stock 1 2 3 4 3 $java Stock 4 3 2 1 0 $java Stock 1 2 3 2 1 2 $java Stock 1 10 1 9 $java Stock 1 10 1 50 1 49

**3. Knapsack** Show the table generated by the Knapsack problem dynamic programming solution that was covered in class. The items and their weights are as follows: (i,v,w), (1,1,5), (2,4,4), (3,3,6), (4,5,3). What is the subset that yields the maximum value for a weight limit of 10?

Submit your table as a .csv file called “knapsack.csv” that is comma separated (when you submit it to users, cat the file to make sure it looks like “0,0,0,0,…”)

**Due:** 7/9 @5pm. Submit the code to users in a hw3 folder. Each question is 3 points and then 1 points for how easy it is to grade.