That’s a famous quote about dynamic programming from George Santayana. Those who cannot remember the past are doomed to repeat it. Those who do not know what dynamic programming is will not feel the answers to true life. Today, we are going to share the philosophy of life behind dynamic programming from AlgoMonster.
the famous quote about dynamic programming
[2] Case study to dynamic programming
Let’s say you are a greedy thief with a 35-pound backpack, waiting at the mall for an opportunity to steal various items that can fit in the bag. Which algorithm would you use as you try to fill the backpack with the highest value items? Again, you adopt a greedy strategy, which is very simple.
(1) Steal the most expensive item that can fit in your backpack.
(2) Then steal the most expensive item that can also fit in the backpack, and so on.
You can steal the following three items: a 30-pound radio worth $3,000, a 20-pound laptop worth $2,000, and a 10-pound tablet worth $1,000. How would you choose?
[2] Dynamic Programming
Dynamic programming teaches us that we need to find solutions to sub-problems, to solve more significant problems in our daily lives after combination. At the same time, we must remember the answers to previous subproblems (memorization) because sometimes the number of repeated subproblems grows exponentially.
We must optimize each day.
To reach your goal, you start from the beginning, and there are many paths, then you check all of them and find which one is the right one.
It is always helpful to solve and learn the problems in your life (list the overlapping sub-problems). If you already know the solution to a problem, you will save a lot of time. There is no big problem in life actually. It looks big because it is just a combination of subproblems. For example, learning to ride a bike used to be a problem. But if you didn’t solve that problem, you couldn’t ride a bike.
Conversely, we can say that if you face a problem, try to find out what it is. For example, suppose you want to get the offer you like. It is a big problem. But if you analyze it, you have to solve the problem in three subjects: Physics, Chemistry, and Mathematics. To solve problems in these subjects, you have to solve problems in different sections of each subject. you must solve the problem for a different topic in each subject. To save time, keep a record of common issues (tabulated again as you work), such as atomic structure in modern physics and physical chemistry.
Dynamic programming is all about remembering the past. It tells you to learn from past experiences and not to repeat the same mistakes in your life.
Greed and choosing the best available options at the moment is not always good. There are times in life when you have to make choices that seem less promising at the moment, but in the future, these will bring the most desirable results.
Solve multiple minor problems in life to make life better. (Best sub-structure)
[3] Overlapping subproblems in dynamic programming
It’s learning from past experiences and we should not repeat the same mistakes.
[3] Optimal substructure in dynamic programming
You need to take life’s big problems one step at a time. Solving multiple minor problems often makes more significant, complex issues easier.
The solution to sub-problems is experiencing, which we gather throughout our lives and use when needed. All the knowledge, mistakes, and experiences we gain on the journey will lead us to our destination.
In addition, once we have mastered the solution to a small problem, we can quickly solve the more significant problem. In life, if we solve our problems first, then our friends/family’s problems, and then gradually our society’s problems, things will become easier.
[3] Optimal principle in dynamic programming
The best immediate decision depends only on the current state, not on how you arrived at it. This principle tells us that there is no need to feel regret for whatever choice you made before. It is what it is, and only make your best plans for the future. If you believe that life has Markovian properties, you will come to the same conclusion.
Start with purpose in mind. The way dynamic programming algorithms solve problems is through backward computation. It provides computational convenience. The exact effectiveness and efficiency will meet expectations if one starts programming his goal achievement journey with a goal in mind and calculates backward.
Life is more probabilistic than deterministic: what you do does not always lead you to the desired outcome, so even if you do the right thing, be prepared to be disappointed when things don’t go your way.
[2] Greedy algorithm
Perfection might be the enemy of excellence. Sometimes, you need to find an algorithm that can roughly solve the problem, and greedy algorithms can come in handy because they are easy to implement and yield results.
The backpack problem mentions the greedy algorithm. When the backpack can take a limited number of things, it is better to take the one that can fit into the bag with the greatest value. Although it is not necessarily the optimal solution, it is an excellent approximate solution.
Being greedy and choosing the best we can is not always good. There are times in life when you have to make choices that seem less promising at the moment, but in the future, these will lead to the most desirable results.
Dynamic programming is a perfect example of how the “greedy” strategy is rarely optimal in life.
It shows you that you can’t always make short-sighted decisions that seem best at the moment. Sometimes you have to sacrifice immediate benefits to get the most desirable outcome in life in the long run.
Also, it tells you that whoever doesn’t remember past mistakes is bound to repeat them! So, you either learn from your mistakes or continue to repeat them, leading to exponential suffering.
[2] Final words
Daily life is a sub-problem of life, representing a practical problem. To get the best results from life, you must make each sub-problem (the current everyday life) optimal. In other words, if you are doing well in every moment of your life today, then you will get the best results in the future.
The point of this is that life is a journey, not a destination. Go to cherish our life.