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

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

Foreman,A Open Source Project

  1. What is Foreman? Foreman is an open source project that helps system administrators manage servers throughout their lifecycle, from provisioning and configuration to orchestration and monitoring. Using Puppet, Chef, Salt, Ansible and Foreman’s smart proxy architecture, you can easily automate repetitive tasks, quickly deploy applications, and proactively manage change, both on-premise with VMs and bare-metal or in the cloud. Foreman provide comprehensive, interaction facilities including a web frontend, CLI and RESTful API which enables you to build higher level business logic on top of a solid foundation. The Foreman interface is very easy to use and user friendly. As your organization grows, so does your workload — and the IT resources required to manage it. There is no “one-size-fits-all” system management solution, but a centralized, open source tool such as  Foreman  can help you manage your company’s IT assets by provisioning, maintaining, and updating hosts th...
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