Back

The Anatomy of Dynamic Programming [with Codes and Memes]

11min
1

It is acceptable that most programmers do not know an excessive amount of algorithms and development methods. Since after successfully passing the job interview to a developer position, the need to simply “code” and create ordinary “working” business applications erases all the theoretical remains in the head.

Moreover, all this knowledge has already been implemented in most libraries in almost all languages. So why even bother with algorithms?

The main difference between an ordinary programmer and a software engineer is a more profound understanding of computer science (including knowledge of algorithms and methods for their evaluation) and paradigms in development.

Facing non-trivial tasks, one gets the available screwdrivers and keys and plunges, while the other opens the book and reads what a screwdriver is. Dynamic programming is a time-tested screwdriver that can unscrew even very tight bolts. Below we prepared for you the best examples of dynamic programming. But let’s start with the basics.

2

What is Dynamic Programming?

How to describe dynamic programming… Well, it is when we have a task that is quite incomprehensible. Therefore, we divide it into smaller tasks… which are also incomprehensible.

Dynamic programming is an algorithmic technique for solving problems based on a recurrent formula and a set of starting states.

Sub-solutions to the problem are formulated from those found in earlier steps. The most pleasant thing about this technique is that the solution has a faster polynomial complexity than naive methods (brute-force).

If you need experienced developers to handle Salesforce migration, integration, or other task, don’t hesitate to reach out to Synebo. 

History of Dynamic Programming

The first association with dynamic programming is olympiad programming. Even though the method was tested in solving economic problems by Richard Belman for the first time, Belman (mathematician) formulated this approach to mathematical optimization and all the necessary conditions for applicability in difficulties.

The original version considered planning a multi-period production process at tiny steps and time points. Step by step, it was required to keep track of how the decisions made in production at previous actions reflected on the company’s further success and what to do next not to fail: buy a factory, sell timber, go offshore.

The optimality principle of Belman sounds like: the optimal policy has the property that regardless of initial states and initial decisions are taken, the remaining solutions should represent the optimal policy concerning the state resulting from the first solution. Hence, it’s also called the optimal substructure

Dynamic Programming Problems

3

The problem has an optimal substructure if its optimal solution can be rationally compiled from the optimal solutions of its subtasks. The presence of the optimal substructure in the issue is used to determine the applicability of dynamic programming and greedy algorithms for solving this problem.

For example, the problem of finding the shortest path between some vertices of a graph contains an optimal solution of subtasks. Many problems solved by dynamic programming can be defined as searching in a given oriented acyclic graph of the shortest path from one vertex to another.

Depending on the formulation of the problem, whether dynamic programming on a segment, on a prefix, on a tree, the optimality term for subproblems can be different. But it is generally formulated as follows: if there is an optimal solution for some subtask that arises in solving the problem, then it should be used to solve the problem in general.

4
Problem definition

During the process of compiling dynamic programming algorithms, it is required to follow a sequence of four actions:

  1. First, describe the structure of the optimal solution.
  2. Recursively determine the value of the optimal solution.
  3. Calculate the value of the optimal solution using the method of bottom-up analysis.
  4. Make an optimal decision based on the received information.

Dependence of the elements of dynamics can be directly given in a condition (this usually happens if this is a problem for numerical sequences). Otherwise, you may find some known number series (like Fibonacci numbers) by manually calculating the first few values. If you are not lucky, you will have to think.​

Are you interested in exploring how to send emails via Outlook API from Salesforce Org? Read another our guide. 

Recurring Formulas

6

Given: initial states (a0 = a1 = 1), and dependencies. The only difficulty that can arise is the understanding that 2n is a parity condition for a number, and 2n + 1 is an odd number. Basically, we need to check whether the number is even and make calculations according to different formulas.

Recursion Vs. Loop

7

The recursion or cycle is a constant problem of choice when implementing the algorithm for a solution. The recursion arises from the condition of the problem (a repeating formula, etc.). Usually, it works perfectly, and you can implement it quickly and easily.

Sequential computation

Now let’s get back to where we started – the recursion is slow. It’s not too slow to bring real troubles, but it might become a problem in tasks where every millisecond is critical.

The main but not the only drawback of the method of sequential computation is that it is suitable only if the function refers exclusively to the elements in front of it. Our problem satisfies this condition.

The essence of the method is as follows: we create an array of N elements and sequentially fill it with values.

Recursive Solution with Value Caching

8

The idea of memoization is elementary – once calculating the value, we put it in some data structure. Then, before each calculation, we check whether a computed value is presented in this structure, and if it is there, we use it.

You may use an array filled with flag values as the data structure. However, if the element value by the index N is equal to the flag’s value, then we probably have not calculated it yet. This creates particular difficulties because the value of the flag should not belong to the set of values of the function, which is not always obvious.

A hash table is a good choice – all actions in it are performed for O (1), which is very convenient. However, two numbers can have the same hash with many values, which, naturally, causes problems. In this case, it is worth using, for example, an RB tree.

Typical Task

9

A ball starts jumping down to the bottom at the top of the ladder, containing N steps. The ball can jump to the next step or jump over one or two steps. (for instance, if the ball is on the 8th step, it can move to the 5th, 6th, or 7th.) First, determine the number of possible “routes” of the ball from the top to the ground.

The idea of ​​a solution. The first step can be accessed only by making a jump with a length equal to one. The second step can be reached by jumping to 2 or only two options from the first step. Finally, the third step can be reached by jumping three, from the first or second.

Specifically, there are only four options (0-> 3; 0-> 1-> 3; 0-> 2-> 3; 0-> 1-> 2-> 3). Considering the fourth step, you can get there from the first step – one route for each route to it, with the second or third – the same. In other words, the number of ways to the 4th step is the sum of the routes to the 1st, 2nd, and 3rd steps. Mathematically, F (N) = F (N-1) + F (N-2) + F (N-3).

2-d Dynamic

10
11
12

In the rectangular table NxM in the beginning, the player is in the left upper cell. They’re allowed to move to the next cell in one move, either to the right or down. However, it is forbidden to move to the left and upwards). So you have to calculate how many ways a player has to get to the right lower cell.

The logic of the solution is completely identical to the problem with the ball and ladder – but now it is possible to get into the cell (x, y) from cells (x-1, y) or (x, y-1). Totally F (x, y) = F (x-1, y) + F (x, y-1). In addition, it is possible to understand that all cells with values (1, y) and (x, 1) have only one route, either straight down or straight to the right.

Are you in need of Salesforce consulting Services? Reach out to Synebo, an experienced provider of Salesforce services.

Explosion Hazard Task

13

When processing radioactive materials, waste forms two types – hazardous (type A) and non-hazardous (type B). The same containers are used for their storage. After placing the waste in the containers, the latter are stacked in a vertical pile.

A stack is considered explosive if more than one type A container in a row. A stack is safe if it is not explosive. Determine the number of possible kinds of safe stacks for a given number of containers “N.”

The answer is (N + 1) – Fibonacci number. You could guess by simply calculating the first 2-3 values. Each primary element is divided into the main (ends with B) and the secondary (ends with A). Then, the side elements are transformed into basic ones (only B can be added to the sequence ending in A).​

Broken Calculator Task

14

A calculator performs three operations: Add to the number X unit; Multiply X by 2; Multiply the number X by 3. First, determine: which least number of operations is needed to obtain “N” from a given number 1. Output this number, and, on the following line, a set of executed operations “111231”.

The naive solution is to divide the number by 3, as long as possible, otherwise by 2, if possible, subtract a unit, and so on until it turns into 1. However, this is a wrong decision because it excludes, for example, the possibility of reducing the number by one and then dividing by three, which causes errors with large numbers (for example, 32718).

The correct solution is to find for each number from 2 to N the minimum number of actions based on the previous elements, basically: F (N) = min (F (N-1), F (N / 2), F (N / 3) ) + 1. It would be best if you remembered that all indices must be integers.

To recreate the list of actions, you need to go in the opposite direction and look for index i when F (i) = F (N), where N is the number of elements in question. If i = N-1, put one at the beginning of the line. If i = N / 2 – put two; otherwise – three.

Golden Pyramid

15
16
17

Imagine a triangle composed of numbers. One number is located at the top. There are two numbers below, then three, and the right to the bottom. So you start at the top, and you need to go down to the bottom of the triangle.

You can go one level down and choose between two numbers under the current position for each move. While walking this path, you “collect” and summarize the numbers you pass. Your goal is to find the maximum amount from different routes.

The first thing that comes to mind is using recursion and calculating all the paths from the top. Then, when we go one level down, all available numbers shape a new smaller triangle, and we can start our function for a new subset and continue this until we reach the bottom.

What if we try to use the principle of dynamic programming and break our problem into many small subtasks, the results of which we can accumulate afterwords. Try to look at the triangle upside down. And now to the second level (penultimate from the bottom).

We can decide the best choice for each cell in our small three-element triangles. Choose the best, summarize with the considered cell and write the result. After all, we will get our triangle, but one level lower.

Repeat this operation again and again. As a result, we need (N-1) + (N-2) + … 2 + 1 operations, and the algorithm’s complexity is N2.

Looking for a trusted provider to assist you with Salesforce development of any kind? Drop Synebo a line and let’s discuss!

What’s Next

18

A “greedy” algorithm, like dynamic programming, is applicable in those cases where the desired object is built from pieces. The “greedy” algorithm at each step, locally, makes an optimal choice.

A simple example is when trying to gain a certain amount by the minimum number of coins. You can consistently type coins with the maximum value (not exceeding the remaining amount). A “greedy” algorithm usually works much faster than an algorithm based on dynamic programming, but the final solution will not always be optimal.

Amortization analysis is a means of analyzing algorithms that produce a sequence of similar operations. Instead of evaluating the operating time for each operation separately, the depreciation analysis estimates the average operating time per transaction.

The difference can be significant if long-running operations are in progress. Depreciation analysis is not only a tool for evaluating algorithms but also an approach to development (this is closely related)

For more information, check our presentation here.

FAQ
When to use dynamic programming?
Use dynamic programming when a problem can be broken down into overlapping subproblems that can be solved independently. It's particularly useful for optimization problems where a solution can be constructed from solutions to subproblems.
What Is dynamic programming algorithm?
A dynamic programming algorithm is a method for solving complex problems by breaking them down into simpler subproblems, solving each subproblem once, and storing their solutions. It combines the solutions of the subproblems to solve the original problem efficiently.
How to solve dynamic programming problems?
To solve dynamic programming problems, first identify the subproblems by breaking down the main problem into smaller, overlapping subproblems. Then formulate a recursive solution to express the problem in terms of its subproblems. Use memoization or tabulation to store the solutions of subproblems to avoid redundant calculations. Finally, use the stored solutions to construct the solution for the original problem.
Table of content
The Anatomy of Dynamic Programming [with Codes and Memes] What Is Dynamic Programming? Dynamic Programming Problems What's next
articles You might be interested in
How to run a Salesforce Health Check
18 Apr 2024
How-to Guides and Tutorials
How to Run a Salesforce Health Check
Yana Pushkar
Yana Pushkar
16 min
A comparative analysis of managed vs unmanaged package Salesforce
15 Apr 2024
Salesforce development
A Comparative Analysis of Managed vs. Unmanaged Package Salesforce
Synebo
Synebo
13 min
How much does it cost to hire a salesforce consultant
08 Apr 2024
Salesforce development
How Much Does it Cost To Hire a Salesforce Consultant?
Andrii Kliuchka
Andrii Kliuchka
12 min
What Is the Difference Between Marketo Engage and Salesforce Marketing Cloud?
01 Apr 2024
Salesforce development
What Is the Difference Between Marketo Engage and Salesforce Marketing Cloud?
Synebo
Synebo
8 min
Salesforce B2B commerce cloud
29 Mar 2024
Salesforce development
Salesforce B2B Commerce Cloud: Benefits, Features and Implementation
Synebo
Synebo
8 min
Salesforce Sales Cloud vs Salesforce Service Cloud_ What’s The Difference
25 Mar 2024
Salesforce development
Salesforce Sales Cloud vs Salesforce Service Cloud: What’s The Difference?
Synebo
Synebo
10 min
Best ways to use chatgpt in Salesforce
20 Mar 2024
Salesforce development
Best Ways to Use ChatGPT in Salesforce
Synebo
Synebo
8 min
Why saas compnies need salesforce
19 Mar 2024
Salesforce development
Why SaaS Companies Need Salesforce
Andrii Kliuchka
Andrii Kliuchka
11 min
Salesforce Marketing Cloud account engagement vs marketing cloud
14 Mar 2024
Salesforce development
Marketing Cloud Account Engagement (Pardot) vs Marketing Cloud: What’s the Difference?
Synebo
Synebo
9min
Salesforce-Marketing-Cloud_-2-scaled
26 Feb 2024
Salesforce development
Salesforce Service Cloud Implementation – Complete Guide
Olexander Orlуk
Olexander Orlуk
14 min
Complete-Guide-scaled
14 Feb 2024
How-to Guides and Tutorials
Complete Guide to Salesforce Testing
Yana Pushkar
Yana Pushkar
16 min
35
17 Jan 2024
What is Salesforce Experience Cloud, and What You Get From It?
Yana Pushkar
Yana Pushkar
10 min
1
05 Jan 2024
How-to Guides and Tutorials
How to Send Emails via Outlook API from your Salesforce Org
Anastasia Sapihora
Anastasia Sapihora
7 min
1
27 Dec 2023
How to Improve Your Business With Salesforce Custom Development?
Yana Pushkar
Yana Pushkar
7min
Salesforce Marketing Cloud
26 Dec 2023
Salesforce development
Salesforce Marketing Cloud: Complete 2024 Guide
Yana Pushkar
Yana Pushkar
11 min
1
22 Dec 2023
21 Best Nonprofit Software Tools to Enhance Your Work
Kristina
Kristina
16 min
1
17 Dec 2023
The Anatomy of Dynamic Programming [with Codes and Memes]
Olexander Oleksiyenko
Olexander Oleksiyenko
11min
Working with salesforce files: the basics
13 Dec 2023
How-to Guides and Tutorials
How to Work With Salesforce Files: The Basics
Olexander Orlуk
Olexander Orlуk
14 min
1
11 Dec 2023
Commerce Cloud B2B vs. B2C. What Is the Difference?
Yana Pushkar
Yana Pushkar
5 min
1
09 Dec 2023
What is Salesforce Flow, and Why Do You Need It?
Sergii Romashov
Sergii Romashov
5 min
15 Types of Salesforce Clouds
04 Dec 2023
15 Types of Salesforce Clouds
Yana Pushkar
Yana Pushkar
11 min
No image available
21 Nov 2023
How-to Guides and Tutorials
How to Get Listed on Salesforce AppExchange
Yana Pushkar
Yana Pushkar
12 min
No image available
14 Nov 2023
Salesforce development
20 Questions to Ask Your Potential Salesforce Implementation Partner
Andrii Kliuchka
Andrii Kliuchka
12min
Cover and internal images for blog post the role of communication in outsourcing teams
07 Nov 2023
Salesforce development
Mastering Communication: Strategies for Collaborating with Salesforce Development Outsourcing Team
Pavel Vehera
Pavel Vehera
13 min
Tips for choosing the right salesforce consulting partner
31 Oct 2023
Salesforce development
How to Choose the Right Salesforce Consulting Partner?
Pavel Vehera
Pavel Vehera
11 min
1 (1)
24 Oct 2023
Salesforce development
How to Build an App for Salesforce AppExchange
Yana Pushkar
Yana Pushkar
14 min
36
02 Aug 2023
Salesforce Implementation: Main Challenges and Best Practices
Yana Pushkar
Yana Pushkar
14 min
image (1)
30 Jul 2023
All Whats and Whys of Ecommerce Automation With the Power of Salesforce
Alina
Alina
4 min
1
20 Jul 2023
CI/CD: Transforming Salesforce Development with DevOps
Alina
Alina
16min
33
31 May 2023
How and Why to Use Salesforce for Nonprofits?
Alina
Alina
6min
1
27 Apr 2023
Main Benefits of Classic to Lightning Migration
Alina
Alina
4min
1
27 Apr 2023
Salesforce Sales Cloud from A to Z
Alina
Alina
6min
1
30 Mar 2023
Salesforce Licenses: How to Understand and Choose?
Alina
Alina
6min
1
04 Mar 2023
What is Salesforce Product Development Outsourcer (PDO)?
Yana Pushkar
Yana Pushkar
5min
1
25 Jan 2023
CMS Hub: The Guide to Managing Your Website
Kristina
Kristina
10min
1
06 Dec 2022
5 Examples of the Best CRM for Nonprofit Organizations
Alina
Alina
5min
1
04 Nov 2022
What Is Hybrid Work, And How to Make It Work?
Alina
Alina
5min
1
24 Oct 2022
Social Media CRM, or How to Get Closer to Your Customers
Alina
Alina
4min
1
27 Sep 2022
Hows, Whys, and Whats of AI in CRM
Alina
Alina
4min
1
30 Aug 2022
What is Beneficial in CRM for Nonprofits?
Kristina
Kristina
7min
1
05 Aug 2022
Salesforce Security in Plain Words
Alina
Alina
7min
1
20 Jul 2022
How to Manage Remote Teams Without Controlling
Synebo
Synebo
9min
1
11 May 2022
How to Reduce Customer Churn Using Salesforce?
Kristina
Kristina
14 min
1
08 Apr 2022
We Help Ukrainians Take the Salesforce Developer Course
Kristina
Kristina
4min
1
24 Jan 2022
Hybrid App Development: Top 3 Frameworks for 2022
Synebo
Synebo
5min
2
17 Dec 2021
Ecommerce Business Automation: the Ultimate Guide for 2022
Kristina
Kristina
19min
1
02 Dec 2021
How to Choose a CRM System for Your B2B Company?
Adelina
Adelina
18min
1
10 Aug 2021
How to Find the Best Company for Developing Your Org in Salesforce
Synebo
Synebo
3min
1
29 Mar 2019
4 Reasons Why You Shouldn’t Be Afraid of Outsourcing Software Development
Synebo
Synebo
4min
1
28 Jul 2018
3 Steps for Salesforce App Development Lifecycle
Synebo
Synebo
4min
phone