美文网首页
Dynamic programming

Dynamic programming

作者: Ivan_lqc | 来源:发表于2015-04-22 19:16 被阅读56次

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];

}

相关文章

  • Chapter 4

    Chapter 4: Dynamic Programming Dynamic programming comput...

  • 18/10/2019 Lecture3: Planning by

    Planning by Dynamic Programming Dynamic Programming 具有某种时...

  • 动态语言/静态语言/动态类型语言/静态类型语言的差异

    动态语言(dynamic programming language): programming behaviors...

  • Dynamic Programming

    研究生学过DP,当时觉得还挺简单的,就是从初始状态开始,找到推导公式一步步往下推嘛。但实际刷题时发现DP还是很难的...

  • dynamic programming

    本质 : 记忆化搜索避免重复计算 多重循环vs记忆化搜索多重循环:可以不用递归 可以对空间复杂度进行优化 步骤:初...

  • Dynamic Programming

    planning all the time.Find a polynomial time. 动态规划背后的基本思想...

  • Dynamic Programming

    70. Climbing Stairs : Easy198. House Robber : Easy121. ...

  • Dynamic programming

    本文针对两篇优秀动态规划文章中存在的不易理解的部分:状态、状态转移的定义和状态转移方程的编程实现部分进行个人解读。...

  • Dynamic Programming

    DP 基本有两个模板: 自上而下:先有最初的结果,求出最后的结果。 自下而上: 先有最后的结果,然后求出最初的结果...

  • Dynamic programming

    Today, I'm going to talk something detailed about dynamic...

网友评论

      本文标题:Dynamic programming

      本文链接:https://www.haomeiwen.com/subject/loiufttx.html