---
# System prepended metadata

title: 'Homework 20 February, 2022'

---

# 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`
