Application of dynamic programming in real world programming [closed]

Question

I have found that dynamic programming is a bit skillful and demanding. But since I expect myself to become an adequate software engineer, I am wondering in which development scenario will DP massively be used or in other words are there any practical usage of it in development based on modern computers?

If you think about design patterns like Proxy pattern and dynamic proxy, which is broadly used in spring framework, DP seems like it is only useful in tech interview.

Also, application of parallelized computing and distributed system seems not easy to empower DP in modern computer context.

Are there any not rare scenarios where DP is widely used in very practical ways? Please forgive my ignorance, since I haven't meet DP in real production level development, which makes me doubt the meaning of digging into DP.

Answer 1

I agree with @ Matt Timmermans.

You don't learn about DP in case you have to use DP someday. By practicing DP, you learn ways of thinking about problems that will make you a better developer. In 10 years, nobody will care about the spring framework, but the techniques you learned from DP will still serve you well.

Now, the answer to your questions, part by parts:

1) Why DP if we have modern computers?

I think you got confused by the analogy of modern computers and the need for DP. Although modern computers are powerful in processing, you may think why I need DP if I have modern fast processors to run my application on.

Not every task can be executed on these modern computers as they come up with storage, network, and compute costs. In fact, as an engineer, we should be thinking of optimizing the usage of such resources, that is, making your code efficient to make it capable of running on minimum system configurations.

In today's world, we have a shared service architecture. It means that different independent services share resources. But the fact is they are interdependent indirectly. Imagine what will happen if a non-optimized code is consuming a lot of memory and compute time. These processors will face difficulty in allocating resources for other services or applications.

The thing is, "Why should I buy an apartment if a multi-bedroom flat can meet my needs and also creates an opportunity for others to buy a flat in the same apartment?"

2) DP in tech interviews

The fact that makes DP the most challenging topic to ace is the number of variations in DP.

It checks your ability to break down a difficult task into small ones to avoid reputations and thus save time, efforts, and thus overall resources.

That is one of the most prime reasons why DP is part of tech interviews.

Not only DP teaches you to optimize and learn useful things, but it also highlights bad practices of writing codes.

3) Usage of DP in real life

1. In Google Maps to find the shortest path between source and the series of destinations (one by one) out of the various available paths.

2. In networking to transfer data from a sender to various receivers in a sequential manner.

3. Document Distance Algorithms- to identify the extent of similarity between two text documents used by Search engines like Google, Wikipedia, Quora, and other websites

4. Edit distance algorithm used in spell checkers.

5. Databases caching common queries in memory: through dedicated cache tiers storing data to avoid DB access, web servers store common data like configuration that can be used across requests. Then multiple levels of caching in code abstractions within every single request that prevents fetching the same data multiple times and save CPU cycles by avoiding recomputation. Finally, caches within your browser or mobile phones that keep the data that doesn't need to be fetched from the server every time.

6. Git merge. Document diffing is one of the most prominent uses of LCS.

7. Dynamic programming is used in TeX's system of calculating the right amounts of hyphenations and justifications.

8. Genetic algorithms.

Also, I found a great answer on Quora which lists the areas in which DP can be used:

Operations research, Decision making, Query optimization, Water resource engineering, Economics, Reservoir Operations problems, Connected speech recognition, Slope stability analysis, Using Matlab, Using Excel, Unit commitment, Image processing, Optimal Inventory control, Reservoir operational Problems, Sap Abap, Sequence Alignment, Simulation for sewer management, Finance, Production Optimization, Genetic Algorithms for permutation problem, Haskell, HTML, Healthcare, Hydropower scheduling, LISP, Linear space, XML indexing and querying, Business, Bioinformatics