Top 6 Problems Helpful for Your Dynamic Programming

Dynamic Programming is a mathematical method to optimize the Multistep Decision Process, which divides the whole problem into several backward and forward spatial and temporal phases according to the characteristics of time or space. It represents the multi-stage decision problem as a series of related single-stage decision problems. Then the multi-stage decision problem becomes a series of single-stage decision problems and then solved one by one to find out the best decision sequence of the whole issue. It emphasizes the continuity of time and space.

Please find below the top 6 classical problems that can be solved using Dynamic programming at algo.monster on articlevibe.com.

1. Regular jumping steps

A frog can jump up 1 step at a time or two steps. Find out the total number of ways the frog can jump on an n-step (the order is different; the result is different).

Try to solve it with dynamic programming.

We can reach the i-th stair by taking one more step from the i-1 and i-2 stairs, i.e., the number of ways to reach the i-th stair is the sum of the number of ways to reach the i-1 and i-2 stairs. So the recurrence formula can be derived as: dp[i]=dp[i-1]+dp[i-2]

Considering that dp[i] is only related to dp[i – 1] and dp[i – 2], so only two variables can be used to store dp[i – 1] and dp[i – 2], making the original O(N) space complexity optimized to O(1) complexity.

2. Perverted step-jumping

A frog can jump up 1 step at a time and jump up two steps. It can also jump up n step. Find the total number of ways the frog can jump on an n-step.

Try to solve it with dynamic programming.

(1) Each height of the step can be completed in one step, so there is one basic solution for each position dp[i]=1

(2) The basic solution, the completed solution for each height, is also and only affected by the previous neighboring height dp[i-1].

(3) Therefore, the final solution of each height is the solution of the previous number () + its basic solution. That is, dp[i]=1+dp[i-1];

3. Rob a row of houses

You are a professional thief who plans to steal houses along the street. Each home has a certain amount of cash hidden in it. The only constraint affecting your theft is the neighboring houses with interconnected security systems. If a thief breaks into two adjacent houses on the same night, the system will automatically alert you. Given a non-negative integer array representing the amount stored in each place, calculate the maximum amount you can steal without setting off the alarm device.

Try to solve it with dynamic programming.

(1) The thief cannot break into adjacent rooms. If you steal i, you cannot steal i-1.

(2) Then if i is the last room in a row, then the maximum amount of walking through the current i rooms is

dp[i]=max(dp[i-2]+numms[i],dp[i-1]);

Therefore, two values dp[i-1],dp[i-2] are also needed.

4. Rob a circle of houses

(the first and the last place in the process are adjacent to each other)

You are a professional thief and plan to steal houses along the street, each with a certain amount of cash hidden inside. All homes in this place are in a circle, which means that the first and last houses are next to each other. At the same time, the neighbouring houses are equipped with interconnected security systems so that if the burglar broke into two adjacent houses on the same night, the system will automatically alert the police. Given a non-negative integer array representing the amount of money stored in each house, calculate the maximum amount you can steal without setting off the alarm device.

Try to solve it with dynamic programming.

(1) First, consider the linear case. When there are a total of i rooms, steal i, you can no longer steal i-1. You can only steal i-2.

So dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]);

(2) In the case of the circular path, consider it based on the linear type because the first and the last become adjacent, so:

You can’t steal the last one after stealing the first one.

Steal from the second one before you can steal the last one.

Therefore, the largest of these two paths can be the final result value.

5. Big cows giving birth to a calf problem

Suppose a mature cow on the farm gives birth to 1 heifer every year and never dies. In the first year, there is one heifer, and from the second year onwards, the cow starts to give birth to heifers. Each heifer is mature enough to give birth to another heifer after three years. Given an integer N, find the number of cows after N years.

Try to solve it with dynamic programming.

(1) In the first three years, only the female cow can give birth.

(2) Since all cows do not die, all cows dp[N-1] in year N-1 will live to year N.

(3) Because mature cows will give birth to 1 heifer each year. Therefore, all cattle in years N-3 will have an additional heifer by year N. dp[N-3].

After N years, the total number of cattle is the consistently large heifer dp[N-1] + the new heifer dp[N-3].

6. Knapsack problem

The problem describes that there are n items, each weighing w[i], whose value is v[i], and now there is a backpack with capacity m, how to choose the items so that the value of the items loaded into the maximized bag.

If we violently enumerate all the permutations and find the largest group, the time complexity is O(2n), and we solve this problem with O(mn) time complexity.

First, set a two-dimensional array dp[][] such that dp[i][j] denotes the maximum value that can be obtained by loading the first i items into a backpack with capacity j. By setting such a two-dimensional array, dp[i][j] denotes the maximum value obtained by loading the first i items into a backpack with capacity j. By setting such a two-dimensional array, the array dp[n][m] values solve the 0-1 backpack problem.

When considering only the i-th item, the situation can be two types of whether to put in the i-th item or not.

For a backpack’s capacity j. f the i-th item is not in it, then the problem becomes the issue of putting the first i – 1 item into a backpack of capacity j.

For a backpack with capacity j, if the i-th item is in it, the current backpack capacity becomes j – w[i], and the value v[i] of this item get the requirement. Then this problem is transformed into the issue of putting the current i – 1 item into a backpack with capacity j – w[i].

When transferring, note whether the value of j-w[i] is non-negative. If it is negative, the current capacity cannot fit the ith item and cannot transfer.

Consider the boundary case again.

If zero items are in the bag, the value must obtain zero, regardless of the backpack’s capacity.

If the backpack’s capacity is 0, it can load no item, and the value must also be 0.