A road named NoNameUno

Suppose there is a train system that goes from station 1 to destination station N. Name the stations as you wish instead of 1, 2, ... N. You are suppose to get a ticket that minimize cost to go from 1 to N. The costs of the fairs going from i to j station is given as Cij, i < j.

 Based on the cost matrix C, we can see that we could draw a graph. Please try simple train system like: 3 stations, and see.

 First thing we need to comeup with a functional equation. In order to arrive at N station, we have to get to some intermediate station, and from their we need one more step to get to N.

Lets F(i,j) = Minimal cost from station i to j, i < j;  Then

F(i,j) = min { F(i, j-1) + C<j-1, j>  ;  C<i,j>  }, where C<i,j> is the fair to go from Ci to Cj

Now is the time for a try ...

//

//  TicketMaster.c

//  DP

//

//  Created by Admin on 5/10/18.

//  Copyright © 2018 AdminProkash Sinha. All rights reserved.

//

/*

 * TicketMaster is usually a person who gives you ticket to your destination station from the station you are now.

 *

 * U R given a simple railroad with stations 1, 2, 3, ... N. U R going from station 1 to N, and between each pair of

 * stations (i,j), s.t. i < j there is a cost per ticket c(i,j). How do you minimize the cost of your travel from 1 to N

 * In general minimize the cost from i to j.

 *

 * This can be represented as Directed Acylic Graph (DAG). Try drawing a simple graph on 3 station to have the feel.

 * In Algos, and in general in Math, it is essential to find the nature of the problem, categorize if possible, classify

 * to a know group of problmes, finally find a pattern or two and possibly reduce it to know problem.

 *

 * It surely looks like shortest path problem, since length and costs are interchangeable. Also it looks like a staged

 * DP problem. Once we understand this much, it is time to comeup with Functional equation for the DP or just a

 * recursive formulation of the problem. NOTE: While DP problems are   back-tracking  in nature, recursive are bottom up

 * also depends on how you look at.

 * FUCTIONAL EQUATION ::

 *

 * Let F(i,j) = Minimal cost to travel from i to j, s.t i<j. Then

 *

 * F(i,j) = Min { F(i, j-1) + C(j-1, j); C(i,j) }

 *          i<j

 *

 * As you can see this is the recursive formulation !! Why? Because it is not using any intermediate calculations !!

 * Can we memoize the intermediate computations ? I'm not sure though, just will have to play around with some

 * concret example

 */

#include <stdio.h>

unsigned int Min ( unsigned int a, unsigned int b)

{

    return ( a < b ? a : b);

}

unsigned int C[4][4] = {

    {9999, 4, 6, 14},

    {9999, 9999, 5, 7},

    {9999, 9999, 9999, 3},

    {9999, 9999, 9999, 9999}

};

unsigned int TicketMaster(unsigned i, unsigned j)

{

    int highNo = 999999;

    if ( i >=j){

        return highNo;

    }

    int result =  Min ( TicketMaster(i, j-1) + C[j-1][j],  C[i][j]) ;

    printf( "result=%d, i=%d, j=%d, C[j-1][j] = %d C[i][j]=%d\n", result, i, j, C[j-1][j],  C[i][j]); 

    return result;

}

int main(int argc, const char * argv[]) 

 {

    unsigned int  Minticketcost = TicketMaster(0, 3);

    printf("Minticketcost = %d\n", Minticketcost); 

    return 0;

}

// --- Traces ---

result=4, i=0, j=1, C[j-1][j] = 4 C[i][j]=4

result=6, i=0, j=2, C[j-1][j] = 5 C[i][j]=6

result=9, i=0, j=3, C[j-1][j] = 3 C[i][j]=14

Minticketcost = 9

Note that in this case it is 3 stage process. DP formulation might not be needed !!!