# Homework 20 February, 2022

## Focus on previous days' problems first. If we discussed different solution to one of your coded solution today, focus on understanding and implementing those first.

### Only after covering all previous works, you may practice this dynamic programming problem.

1. **Maximum Sub-Set Sum Non-Adjacent:**
You are given an input array of positive integers. Write a program to output possible maximum sum of non-adjacent subset. Meaning you can sum elements from the array only if elements are not adjacent.
Sample Input: [**75**, 105, **120**, 75, 90, **135**]
Here Output is 75 + 120 + 135 = 330. (picked subset is marked **bold**)

- `[7, 10, 12, 7, 9, 14]` output: `33`
- `[4, 3, 5, 200, 5, 3]` output: `207`
- `[10, 5, 20, 25, 15, 5, 5, 15]` output: `60`

2. **Staircase Traversal:**
Imagine you have traverse a staircase. You have two inputs, both positive integers: `height` and `maxSteps`. `height` is the height of the staircase. `maxSteps` is maximum number of steps at a time you can advance up the staircase. Your goal is to find the total number of different ways we can climb the staircase.

For example: if height = 3 and maxSteps = 2, you could climb the staircase in 3 ways.
- 1 step, 1 step, then 1 step.
- 1 step, then 2 steps.
- 2 steps, then 1 step.

To solve it with dynamic programming, we'll create an array, representing number of different ways we can climb up to that **index**.

For height = 4, maxSteps = 2,

If we draw the staircase,

                _
              _|4
            _|3
          _|2
    _____|1
        0

We'll calculate the array: From 0 to **height**.

| Index | 0 | 1 | 2 | 3 | 4 |
| --------- | --- | --- | --- | --- | --- |
|Ways To Top| 1 | 1 | 2 | 3 | 5 |

`$array[4]` which is `5` is our answer here. Now what is the formula for calculating `$array[i]`? For the provided inputs, draw the staircase, fill up the array and try to find out the formula.
Hint: `$array[0]` = 0, `$array[1]` = 1. These two values are our starting conditions, these will always be same. We also have a `maxSteps` input to take into consideration.

**Input and Outputs:**
- height: `4`, maxSteps: `2`, output: `5`
- height: `10`, maxSteps: `1`, output: `1`
- height: `7`, maxSteps: `2`, output: `21`