Today, I'm going to talk something detailed about dynamic programming. Dynamic programming is a kind of complicated algorithm which involves a lot of algorithm-design thoughts，such as optimal sub-result, recursive, iterative, divide-conquer and so on. I will analyse my own thought by tearing apart the whole packed enigma.
First, the aim of using dynamic programming is reducing the time complexity and sometimes avoiding the unnecessary space-consuming. To solve a problem, the first method which is also the simplest comes to mind is brute-force method. However, brute-force always can't meet the online judge standard. Then divide-conquer algorithm is adopted. A big amount of problems can be solved by divide-conquer. We can understand this algorithm just by the literal meaning. We divide the problem into sub-problems which is small enough to solve directly first, then merge these sub-results into the final result.
Brute-force and divide-conquer are the overview of applied algorithms. For writing code, there are two ways to implement these algorithms, iterative and recursive. The difference between iterative and recursive isn't that clear. In my opinion, iterative way is fast and memory-friendly, but hard to write by code. On the contrary, recursive way is slow and memory-consuming, but easy to implement.
Dynamic programming is an algorithm which is only for the convenience of computer. It's hard for programmer to write, but efficient for computer to implement. It combines the features of divide-conquer and iterative. However, the concept of dynamic programming isn't just divide-conquer and iterative. It's more advanced and harder to understand. Even you understand it perfectly, without enough experience and patience, it's still hard to adopt it in solving a related problem.
I'm going to explain my idea of dynamic programming. If it's flawed, even wrong, please point it out. The key point of dynamic programming is to find the same status for all the small-divided problems and switch the status to the final problem. I will coding out a classic dp problem to interpret the finding and switching process.
Problem: What's the length of the longest incrementing subsequence (not consecutive) in array (1,7,2,3,8,4).
Solution:
int lis(int *arr, int len)
{
//find the status for sub-problem
int *mLen = (int *)malloc(sizeof(int)*len);
mLen[0] = 1;
for (int i=0; i<len; i++)
{
for (int j=0; j<i; j++)
{
//switching the status gradually
if (mLen[j] < mLen[i])
{
mLen[i] = mLen[j] + 1;
}
else
{
mLen[i] = mLen[j];
}
}
}
return mLen[len-1];
}
