Dynamic Programming (DP) Tutorial with Problems

Dynamic Programming

Table of Contents

• 1. Introduction to Dynamic Programming
• 2. Applications
• 3. Steps to solve a DP Problem
• 4. Approaches to Dynamic Programming
• 5. Example: Fibonacci Sequence
• 6. Example: Knapsack Problem
• 7. Leetcode Problems
• 8. References

1 Introduction to Dynamic Programming

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure, which are described below:

• Overlapping subproblems

  A problem has overlapping subproblems if it can be broken down into subproblems which are reused several times. For example, in the Fibonacci sequence, to calculate Fib(5), one needs Fib(4) and Fib(3), but Fib(4) itself requires Fib(3) and Fib(2). Here, Fib(3) is calculated multiple times, which is an overlapping subproblem.

• Optimal substructure

  A problem has an optimal substructure if an optimal solution to the problem contains within it optimal solutions to the subproblems. For instance, in the shortest path problem, if the shortest path from point A to point C goes through point B, then the shortest path from A to B is also part of the shortest path from A to C.

Monotonic Stack

Table of Contents

• 1. Introduction to monotonic stack
• 2. What can monotonically increasing stacks do?
  • 2.1. To find the previous less element of each element in a vector with O(n) time.
  • 2.2. To find the next less element of each element in a vector with O(n) time.
• 3. What can monotonically decreasing stacks do?
• 4. When are monotonic stacks used?
• 5. The applications of monotonic stacks
• 6. References

1 Introduction to monotonic stack

A monotonic stack is a stack whose elements are monotonically increasing or decreasing.

If we pop greater elements from the stack before pushing a new element, the stack will increase from bottom to top. If we pop lesser elements, the stack will decrease.

The typical paradigm for an increasing monotonic stack is like:

for (int i = 0; i < A.size(); i++) {
    while (!stk.empty() && stk.top() > A[i]) {
        stk.pop();
    }
    stk.push(A[i]);
}

2 What can monotonically increasing stacks do?

Monotonically increasing stacks can be used to solve a variety of algorithmic problems. One common use case is for finding the nearest greater element in an array. By maintaining a stack of elements in increasing order, we can quickly determine the next greater element for each element in the array. Monotonically increasing stacks can also be used for finding the maximum area of a histogram, as well as for solving problems related to dynamic programming and graph algorithms.

2.1 To find the previous less element of each element in a vector with O(n) time.

What is the previous less element of an element in a vector? Suppose there is a vector [3, 8, 9, 6], for each element 3, 8, 9, and 6:

• There is no previous less element for 3.
• The previous less element of 8 is 3.
• The previous less element of 9 is 8.
• The previous less element of 6 is 3.

C11 (C standard revision) features

C11 revision

Table of Contents

• 1. Overview
• 2. Multiple threading
• 3. Generic selection
• 4. Alignment facilities
• 5. Static assertions
• 6. Anonymous structs and unions
• 7. Other features
  • 7.1. quick_exit() function
  • 7.2. _Noreturn function specifier
  • 7.3. Bounds-checking functions
  • 7.4. Unicode support
  • 7.5. complex types
• 8. C17 / C18
• 9. C2x
• 10. References

1 Overview

C11 is the informal name for ISO/IEC 9899:2011, the current standard for the C language that was ratified by ISO in December 2011.

It standardizes many features for safer programming, such as removal of gets() function.

Additionally, C11 adds concurrency support, type-generic expressions, alignment-related facilities, static assertion, unicode support, floating-point characteristic macros, no-return functions, anonymous structures and unions, and various bound-checking and reentrancy functions.

The following examples demonstrating C11 features can be compiled with options such as

clang -std=c11 ex.c

2 Multiple threading

C11 standardized multi-threading support.

It introduces new headers threads.h and stdatomic.h, supporting multiple threads of execution:

• threads creation and management
• mutexes
• conditional variables
• atomic objects
• thread specific storage