Dynamic Programming - 1D

Steps for solving DP problem:

  1. Define subproblems
  2. Write down the recurrence that relates subproblems
  3. 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.

Problem link

Decode Ways

Letter to Number

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

1
2
3
4
A -> 1
B -> 2
...
Z -> 26

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

Problem Link

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

Problem Link