Dynamic Programming with profile - introduction

Introduction

Dynamic Programming , or DP for short, is defined by two factors  - state and recurrence.

Two terms can be defined as follow
State : A result produced depending on variable(s). variables to be used and an outcome to be stored depending on the variables need to be determined.

Recurrence : Relationship between each state.


For example, say we are looking for ways to store powers of 5.

State
Variable to be used : exponent
An outcome to be stored depending on the variable : 5^exponent
=> pow[i]  = 5^i

Recurrence
5^i = 5 * 5^(i-1)
pow[i] = 5 * pow[i-1]

After defining state and recurrence, we need to determine value(s) for base case(s).

In the above example, base case is pow[0] = 1.

To code powers of 5,

int power_of_5[N]; //make array size of N
power_of_5[0] = 1;
for(int i=1; i < N; i++)
{
     power_of_5[i] =  5 * power_of_5[i-1];
}


Dynamic Programming looks simple enough. But the seemingly simple algorithm can be used to solve most complicated problems.
And sometimes, it is necessary to tweak or make minor modifications to traditional DP in order to properly handle difficult problems. One of them is DP with profile.


What is Dynamic Programming with Profile?

Dynamic Programming with profile is all about defining three terms : state, recurrence, and profile.

We already know what state and recurrence are from Introduction.
Let's see why we need profile

profile
: Information about other state(s).

You might argue that "state" itself holds information in its outcome and therefore profile is unnecessary.
Yes, true. However, let's look at the definition of state again.

State : A result produced depending on variable(s). variables to be used and an outcome to be stored depending on the variables need to be determined.

Did you notice that I italicized "an"? There is a reason.

What if you need more than one information about a certain state?
You can say that we can do that by some time of customized data structure to hold both data, like pair<int,int> or Node.

Then what if the data are not necessarily related to each other?
More formally, what if for a fixed variable i, DP[i] is different depending on other information?

This is the time to use DP with profile so that we can handle above cases by using DP[i][profile].

I am guessing you are still very much confused, and have absolutely no idea what I am talking about. Do not worry. I will explain them over and over using examples.