Skip to main content

What is Dynamic Programming ?

 




  • What actually dynamic programming is ?

In computer science or mathematics, dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions. Also known as dynamic optimization.

Dynamic programming is similar to divide and conquer only difference is that dynamic programming is used when there is overlapping subproblem property and in divide and conquer there is no overlapping subproblem property.

example, fibonacci series.

When to use dynamic programming ?

Following two attributes suggests that a problem can be solved using dynamic programming :

  1. optimal substructure
  2. overlapping sub-problems.
  • Ways to of using dynamic programming :
  1. Top-Down : Firstly, Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization.
  2. Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Tabulation.
Labels:

Comments

Post a Comment

Popular posts from this blog

CRM, a vast ocean of code I saw

  https://crm.zoho.com/ Head over to the Zoho CRM and see for yourself, well for the first time you will not feel it but as you go deep in it, you will realise the small small things that this CRM has implemented then you will get amazed by this amazing product. As a programmer, I got the chance to look at the vast ocean of code of this ZOHO CRM and experience like I was swimming in the ocean not knowing which way goes to where , I mean literally I was amazed how it has expanded,how it created little little things for its customers, the feeling of debugging it was on another level. I am grateful for the opportunity given by ZOHO to me for working in such a vast product. This CRM that I worked in won many awards, it had gone into Paul Greenberg’s (PG) CRM Watchlist 2022 award against major players like Adobe, Microsoft, Oracle, SAP, Salesforce, and ServiceNow with the highest score and distinction , PCMag.com awards “Business Choice Awards 2019” to Zoho CRM, beating 4 times winner —...
Post a Comment
Read more

Experience Of Summer Internship From Red Hat, Inc.

  About the Author:  Varad Parlikar, a student of Deogiri Institute Of Engineering And Management Studies, Babasaheb Ambedkar Marathwada University, shares how the summer internship helped him to improve his skills in Open Source Domain . He also shares snippets of his Summer Internship experience from Redhat Inc. This year I have had the incredible opportunity to intern for the Redhat Inc.I was in the third year of engineering curriculum of computer science stream,The hunt for the summer internship began.I had always wanted to work with Redhat Group,So I decided to appear for the summer internship program from Redhat,Pune.I submitted my resume for the same and I got shortlisted for the summer internship program at Redhat,Pune.So I travelled for the same to pune as per the schedule of summer internship program. The selection process started off with an aptitude test after which the shortlisted students were interviewed by them.I was asked questions on basic linux knowledge and...
Post a Comment
Read more

Basics Of Ansible,A OpenSource Tech

What is Ansible? Ansible is simple open source IT engine which automates application deployment, intra service orchestration, cloud provisioning and many other IT tools. Ansible uses playbook to describe automation jobs, and playbook uses very simple language i.e.  YAML  (It’s a human-readable data serialization language & is commonly used for configuration files, but could be used in many applications where data is being stored)which is very easy for humans to understand, read and write. Hence the advantage is that even the IT infrastructure support guys can read and understand the playbook and debug if needed (YAML — It is in human readable form). Ansible is designed for multi-tier deployment. Ansible does not manage one system at time, it models IT infrastructure by describing all of your systems are interrelated. Ansible is completely agentless which means Ansible works by connecting your nodes through ssh(by default). But if you want other method for connection like K...
Post a Comment
Read more