# Dynamic Programming - 1D

Steps for solving DP problem:

- Define subproblems
- Write down the recurrence that relates subproblems
- Recognize and solve the base cases

# Maximum Sum of 3 Non-Overlapping Subarrays

In a given array nums of positive integers, find three non-overlapping subarrays with maximum sum. Each subarray will be of size `k`

, and we want to maximize the sum of all `3*k`

entries.

# Decode Ways

#### Letter to Number

A message containing letters from A-Z is being encoded to numbers using the following mapping:

1 | A -> 1 |

Given a non-empty string containing only digits, determine the total number of ways to decode it.

#### Letter and * to Number

Beyond the description above, the encoded string can also contain the character ‘*‘, which can be treated as one of the numbers from 1 to 9.

1 | * -> 1, 2, ..., 9 |