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.