# 4.4. Principles of Dynamic Programming

alg

C_{ij} = the cost of the shortest path from (0,0) to (i,j)
- Then C_{ij} = min \{C_{i-1,j} + w_{i-1, j} ^{s},C_{i-1,j-1} + w_{i-1, j-1} ^{se},C_{i,j-1} + w_{i, j-1} ^{e} \}
Recursive formulation
Optimal substructure
Overlapping subproblems
Bottom-up approach

# 4.4.1. Optimal Substructure (wiki)

Dynamic programming algorithms are often used for optimization.
A problem is said to have optimal substructure
- if a solution to a given optimization problem can be constructed efficiently from optimal solutions of its subproblems.
Consequently, the first step towards devising a dynamic programming solution is to check whether the problem exhibits such optimal substructure.
- Such optimal substructures are usually described by means of recursion.
- C_{ij} = min \{C_{i-1,j} + w_{i-1, j} ^{s},C_{i-1,j-1} + w_{i-1, j-1} ^{se},C_{i,j-1} + w_{i, j-1} ^{e} \}

# 4.4.2. Overlapping Subproblems (wiki)

To solve a problem, we often need to solve different parts of the problem (subproblems), then combine the solutions of the subproblems to reach an overall solution.
A problem is said to have overlapping subproblems if
- the problem can be broken down into subproblems which are reused several times or
- a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems.
- C_{ij} = min \{C_{i-1,j} + w_{i-1, j} ^{s},C_{i-1,j-1} + w_{i-1, j-1} ^{se},C_{i,j-1} + w_{i, j-1} ^{e} \}
The dynamic programming approach seeks to solve each subproblem only once, thus reducing the number of computations:
- (i) once the solution to a given subproblem has been computed, it is stored or "memoized":
- (ii) the next time the same solution is needed, it is simply looked up.
This approach is especially useful when the number of repeating subproblems grows exponentially as a function of the size of the input.
If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide-and- conquer" instead. This is why merge sort and quick sort are not classified as dynamic programming problems.
C_{ij} = min \{C_{i-1,j} + w_{i-1, j} ^{s},C_{i-1,j-1} + w_{i-1, j-1} ^{se},C_{i,j-1} + w_{i, j-1} ^{e} \}

# 4.4.3. The Checkerboard Problem

Courtesy of Wikipedia
Restrictions
- A checker can start at any square on the first row (i= 1).
- It can move only diagonally left forward, diagonally right forward, or straight forward.
- It must pay the cost c[i] when visiting the (i, j)-position.
Cost table c [i] [j]
Problem
- Given a checkerboard with n \times n squares, and a cost function c[i][j], find the minimum-cost path from the first row to the last row.
Optimal substructure

code

#include <stdio.h> #define N 5
#define INFTY 100000
int c[N + 1][N + 2] = {-1, -1, -1, -1, -1, -1, -1, -1, 7, 3, 5, 6, 1, -1, -1, 2, 6, 7, 0, 2, -1, -1, 3, 5, 7, 8, 2, -1, -1, 7, 6, 1, 1, 4, -1, -1, 6, 7, 4, 7, 8, -1};
int p[N + 1][N + 2], q[N + 1][N + 2];

int min3(int a, int b, int c)
{
    ...
}

void ComputeCBCosts(int n)
{
    int i, j, min;
    for (i = 1; i <= n; i++)
        q[1][i] = c[1][i];
    for (i = 1; i <= n; i++)
    {
        q[i][0] = INFTY;
        q[i][n + 1] = INFTY;
    }
    for (i = 2; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            min = min3(q[i - 1][j - 1], q[i - 1][j],
                    q[i - 1][j + 1]);
            q[i][j] = min + c[i][j];
            if (min == q[i - 1][j - 1])
                p[i][j] = -1;
            else if (min == q[i - 1][j])
                p[i][j] = 0;
            else
                p[i][j] = 1;
        }
    }
}

void PrintShortestPath(int n, int imin)
{
    printf(" (%d, %d) <-", n, imin);
    if (n == 2)
        printf(" (%d, %d)\n", 1, imin + p[n][imin]);
    else
        PrintShortestPath(n - 1, imin + p[n][imin]);
}

void ComputeCBShortestPath(int n)
{
    int i, imin, min;
    ComputeCBCosts(n);
    imin = 1;
    min = q[n][1];
    for (i = 2; i <= n; i++)
    {
        if (q[n][i] < min)
        {
            imin = i;
            min = q[n][i];
        }
    }
    printf("*** The cost of the shortest path is %d.\n", q[n][imin]);
    PrintShortestPath(n, imin);
}

void main(void)
{
    int n;
    n = N;
    ComputeCBShortestPath(n);
}

alg