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

Web Development the Beginning…

  As I mentioned in my latest gift(blog) that  web-development  can be done with the help of many tools such as, 1)  Node.js – open source, runtime environment for developing Web apps 2) AngularJs  — structural framework for dynamic Web apps 3)  Brackets  — a modern, open source text editor 4) Bootstrap  — Javascript framework for developing responsive Web apps 5) LESS  — the dynamic stylesheet language 6) Atom  — a text editor 7) Notepad ++  — a text editor To develop any web application, the things required are, 1) Code Editor  (Text Editor) 2) OS  (Operating System) and 3) Language  (in which we are coding) There are many  web-development   languages  but, the most  popular , easy to  code  and  dynamic  are , 1) HTML (Hypertext Markup Language) 2) CSS (Cascading Style Sheets) 3) XML (EXtensible Markup Language) 4) PHP (Hypertext Preprocessor) 5) SQL (Structured Query Languag...
Post a Comment
Read more