dynamic programming

1. Concept

Dynamic programming: dynamic programming is nothing more than using historical records to avoid repeated calculations. We need some variables to save these history records, usually with one-dimensional array or two-dimensional array.

Three steps of dynamic planning:

1. Define the meaning of array elements. As mentioned above, we will use an array to save the historical array. Suppose we use a one-dimensional array dp[]. At this time, a very important point is to specify the meaning of your array element. For example, what does your dp[i] mean?
2. Find out the relationship between array elements, dynamic programming, which is similar to the induction method in high school. When we want to calculate dp[n], we can use dp[n-1], dp[n-2]... dp[1] to deduce dp[n], that is, we can use historical data to deduce new element values, so we need to find out the relationship between array elements, for example, dp[n] = dp[n-1] +dp[n-2], this is their relationship. And this step is also the most difficult step.
3. Find the initial value. Those who have studied mathematical induction know that although we know the relationship between array elements, such as dp[n] = dp[n-1] + dp[n-2], we can calculate dp[n] through dp[n-1] and dp[n-2], we need to know the initial value. For example, if we push it all the time, dp[3] = dp[2] + dp[1]. dp[2] and dp[1] can no longer be decomposed, so we must be able to directly obtain the values of dp[2] and dp[1], which is the so-called initial value.

2. Case

1, Simple one-dimensional DP

Problem Description: a frog can jump up 1 step or 2 steps at a time. Find out how many jumping methods the frog can jump up an n-step.

(1) Define the meaning of array elements

According to the above steps, first of all, let's define the meaning of dp[i]. Our question is how many jumping methods are required for frogs to jump up n steps. Then we define dp[i] as: there are dp[i] jumping methods to jump up an I step. In this way, if we can calculate dp[n], isn't that the answer we ask for? So the first step is to complete the definition.

(2) Find out the relationship between array elements

Our purpose is to ask dp[n], the problem of dynamic programming, as you often hear, is to divide a large-scale problem into several small-scale problems, and then deduce a large problem from a small problem. In other words, the scale of dp[n] is n, and the smaller ones are n-1, n-2, n-3... That is, dp[n] must have some relationship with dp[n-1], dp[n-2]. We need to find out their relationship.

So the problem comes, how to find it?

How to find this is the most core and difficult one. We must go back to the problem itself and find their relationship. What will dp[n] be equal to?

For this problem, because the situation can choose to jump one level or two levels, there are two ways for the frog to reach the nth step

One is to jump up from level n-1

One is to jump up from level n-2

Since we want to calculate all possible jumps, we have dp[n] = dp[n-1] + dp[n-2].

(3) Find out the initial conditions

When n = 1, dp[1] = dp[0] + dp[-1], and we are an array and do not allow subscripts to be negative. Therefore, for dp[1], we must directly give its value, which is equivalent to the initial value. Obviously, dp[1] = 1. Similarly, dp[0] = 0. (because there are 0 steps, it must be 0 jumping methods). Thus, the initial value is obtained: dp[0] = 0

Note: the analysis is problematic because i=2, dp[2]=2; The fault is that the search for the initial value is not rigorous enough,

int f(int n){
    int[] dp = new int[n + 1];
    // Give initial value
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    // dp[n] is calculated by the relation
    for(int i = 3; i <= n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }
    // Return the final result
    return dp[n];
}

2, DP of two-dimensional array

Problem Description:

A robot is located in the upper left corner of an m x n grid (the starting point is marked "Start" in the following figure). The robot can only move down or right one step at a time. The robot attempts to reach the lower right corner of the grid (marked "Finish" in the following image). How many different paths are there altogether? (m and N values shall not exceed 100)

Still the same, three steps to solve.

Step 1: define the meaning of array elements

Since our goal is how many paths there are from the upper left corner to the lower right corner, we define dp[i] [j] as: when the robot comes to (i, j) from the upper left corner, there are dp[i] [j] paths. Then dp[m-1] [n-1] is the answer we want.

Note that this grid is equivalent to a two-dimensional array. The array starts from subscript 0, so the position in the lower right corner is (m-1, n - 1), so dp[m-1] [n-1] is the answer we are looking for.

Step 2: find out the relationship between the elements of the relational array

Imagine the following, how can a robot reach the position (i, j)? Since the robot can go down or right, there are two ways to get there

One is to take one step from the position of (i-1, j)

One is to take one step from the position (i, j - 1)

Because all possible steps are calculated, all possible paths are added up, so the relationship is dp[i] [j] = dp[i-1] [j] + dp[i] [j-1].

Step 3: find out the initial value

Obviously, when dp[i] [j], if one of I or j is 0, can we still use the relationship? The answer is no, because i - 1 or j - 1 will become negative at this time, and the array will have problems. Therefore, our initial value is to calculate all dp[0] [0.... n-1] and all dp[0.... m-1] [0]. This is very easy to calculate, equivalent to the top row and the left column in the computer diagram. Therefore, the initial values are as follows:

dp[0] [0….n-1] = 1; // Equivalent to the top row, the robot can only go all the way to the left

dp[0…m-1] [0] = 1; // Equivalent to the leftmost column, the robot can only go all the way down

  public static int calc(int m, int n) {
    if (m <= 0 || n <= 0) {
      return 0;
    }

    int[][] dp = new int[m][n];
    for(int i = 0; i < m; i++){
      dp[i][0] = 1;
    }
    for(int i = 0; i < n; i++){
      dp[0][i] = 1;
    }
    for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
      }
    }
    return dp[m-1][n-1];
  }

3, Edit distance

Problem Description: given two words word1 and word2, calculate the minimum operand used to convert word1 to word2.

You can perform the following three operations on a word:

Insert a character

Example 1:
input: word1 = "horse", word2 = "ros"
output: 3
 explain: 
	horse -> rorse (take 'h' Replace with 'r')
	rorse -> rose (delete 'r')
	rose -> ros (delete 'e')

answer

As usual, follow the above three steps, and I can tell you here that 90% of string problems can be solved by dynamic programming, and 90% use two-dimensional arrays.

Step 1: define the meaning of array elements

For our purposes, we seek the minimum number of operands used to convert word1 to word2. Then we define dp[i] [j] as: when the length of string word1 is I and the length of string word2 is j, the minimum number of operations used to convert word1 to word2 is dp[i] [j].

Sometimes, the meaning of array is not easy to find, so I'll give you a routine, and the rest depends on you to understand.

Step 2: find out the relationship between the elements of the relational array

Next, we will find the relationship between dp[i] [j] elements. Compared with other questions, this question is relatively difficult to find. However, no matter how difficult it is, in most cases, dp[i] [j] must have some relationship with dp[i-1] [j], dp[i] [j-1], dp[i-1] [j-1]. Because our goal is to deduce the large-scale from the small-scale through some operations. For this problem, we can do three operations on word1

Insert a character

Since we want to minimize the number of operations, we need to find the best operation. Then there is the following relationship:

1, If word1[i] is equal to word2 [j], no operation is required at this time. Obviously, dp[i] [j] = dp[i-1] [j-1]. Don't forget the meaning of dp[i] [j].

2, If word1[i] is not equal to word2 [j], then we must adjust. There are three kinds of adjustment operations, and we need to choose one. The corresponding relations of the three operations are as follows (pay attention to the difference between string and character):

(1) . if the character word1[i] is replaced with word2[j], then dp[i] [j] = dp[i-1] [j-1] + 1;

(2) . if a character equal to word2[j] is inserted at the end of string word1, dp[i] [j] = dp[i] [j-1] + 1;

(3) If the character word1[i] is deleted, dp[i] [j] = dp[i-1] [j] + 1;

Then we should choose an operation to minimize the value of dp[i] [j]. Obviously, there is

dp[i] [j] = min(dp[i-1] [j-1]，dp[i] [j-1]，dp[[i-1] [j]]) + 1;

So, our relationship was deduced,

Step 3: find out the initial value

Obviously, when dp[i] [j], if one of I or j is 0, can we still use the relationship? The answer is no, because i - 1 or j - 1 will become negative at this time, and the array will have problems. Therefore, our initial value is to calculate all dp[0] [0.... n] and all dp[0.... m] [0]. This is very easy to calculate, because when the length of a string is 0, it is converted to another string, so it can only be inserted or deleted all the time.

public int minDistance(String word1, String word2) {
  int n1 = word1.length();
  int n2 = word2.length();
  int[][] dp = new int[n1 + 1][n2 + 1];
  // Initial value of dp[0][0...n2]
  for (int j = 1; j <= n2; j++) {
    dp[0][j] = dp[0][j - 1] + 1;
  }
  // Initial value of dp[0...n1][0]
  for (int i = 1; i <= n1; i++) {
    dp[i][0] = dp[i - 1][0] + 1;
  }
  // dp[n1][n2] is derived from the formula
  for (int i = 1; i <= n1; i++) {
    for (int j = 1; j <= n2; j++) {
      // If word1[i] is equal to word2[j]. The subscript corresponding to the ith character is i-1
      if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
      }
    }
  }
  return dp[n1][n2];
}

Dynamic programming exercises

From niuke.com

Jump steps

describe

A frog can jump up one step or two steps at a time. Find out the total number of jumping methods for the frog to jump up an n-step step (different results are calculated in different order).

Example 1

Input:

2

Return value:

2

copy

Example 2

Input:

7

Return value:

21

solution

This is a classic recursive problem. You can think, if the frog is currently on the nth step, where was its last step?

Obviously, because it can jump one step or two steps, its previous step must be at step n-1 or step n-2, that is, the number of jumps it jumps to step n is the sum of the number of jumps to step n-1 and step n-2.

If the jump up [external chain picture transfer fails, the source station may have an anti-theft chain mechanism. It is recommended to save the picture and upload it directly (img-2xjp1il9-1632038167)( https://www.nowcoder.com/equation?tex=i&preview=true )]If there are fun(n) jump methods for a step, then there are fun(n) = fun(n-1)+fun(n-2) jump methods for it to jump to N steps.

Then, we think about the initial situation. There is only one jumping method for jumping up one step and two jumping methods for jumping up two steps. Finally, we get the following recursive formula, which is similar to Fibonacci.

Recursion is not recommended in the written test. Fibonacci's solution 2 or solution 3 (improvement of solution 2) can be used

if (target == 1 || target == 2) {
  return target;
}
int a = 1, b = 2, c = 0;
for (int i = 2; i < target; i++) {
  c = a + b;
  a = b;
  b = c;
}
return c;

public static int jumpFloor(int target) {
int a = 1, b = 1;
for (int i = 2; i <= target; i++) {
  a=a+b;
  b=a-b;
}
return a;
}

The problem of maximum cumulative sum of subarrays

describe

Given an array arr, returns the maximum cumulative sum of subarrays

For example, arr = [1, -2, 3, 5, -2, 6, -1], in all subarrays, [3, 5, - 2, 6] can accumulate the maximum sum of 12, so 12 is returned

The title guarantees that there are no numbers that are all negative

Example 1

Input:

[1, -2, 3, 5, -2, 6, -1]

Return value:

12

Solution 1: dynamic programming

  public int maxsumofSubarray(int[] arr) {
    if (arr.length == 0) {
      return 0;
    }
    int[] dp = new int[arr.length];
    dp[0] = arr[0];
    int max = dp[0];
    for (int i = 1; i < dp.length; i++) {
      dp[i] = dp[i - 1] > 0 ? dp[i - 1] + arr[i] : arr[i];
      max=Math.max(max,dp[i]);
    }
    return max;
  }

Dynamic programming improvement

  public int maxsumofSubarray(int[] arr) {
    if (arr.length == 0) {
      return 0;
    }
    int sum = arr[0];
    int max = sum;
    for (int i = 1; i < arr.length; i++) {
      sum = sum > 0 ? sum + arr[i] : arr[i];
      max = Math.max(max, sum);
    }
    return max;
  }

The best time to buy and sell stocks

describe

Suppose you have an array in which the ith element is the price of the stock on day i.
You have a chance to buy and sell. You can't sell a stock until you buy it. Please design an algorithm to calculate the maximum benefit.

Example 1

Input:

[1,4,2]

Return value:

3

Example 2

Input:

[2,4,1]

Return value:

2

Solution 1: dynamic programming

dp[i] represents the maximum profit of the previous I day.

Then the transfer equation is:
dp[i] = max( dp[i-1], prices[i] - min(prices[0 -> i])).

In other words, the maximum daily profit is the greater of the following two items:

• Yesterday's biggest profit
• Buy shares on the day before the day when the share price is the lowest, and sell shares on the day to earn profits

Initial:
dp[0] = 0;

Return value:
dp[prices.length - 1]

public static int maxProfit(int[] prices) {
  if (prices.length == 0) {
    return 0;
  }
  int maxPro = 0;
  int min = prices[0];
  for (int i = 1; i < prices.length; i++) {
    maxPro = Math.max(maxPro, prices[i] - min);
    min = Math.min(min, prices[i]);
  }
  return maxPro;
}

Solution 2: dynamic programming improvement (double pointer)

Use two pointers, one pointer to record the minimum value accessed (note that this is the minimum value accessed), one pointer to go straight back, then calculate their difference and save the maximum value

public static int maxProfit(int[] prices) {
  if (prices.length == 0) {
    return 0;
  }
  int min = prices[0];
  int maxPro = 0;
  for (int i = 1; i < prices.length; i++) {
    min = Math.min(min, prices[i]);
    maxPro = Math.max(prices[i] - min, maxPro);
  }
  return maxPro;
}

Minimum amount of money to change

describe

Given array arr, all values in arr are positive integers and do not repeat. Each value represents a currency with a face value. Any currency with a face value can be used. Given an aim, it represents the amount of money to find, and find the minimum number of currencies that make up the aim.

If there is no solution, please return - 1

[requirements]

Time complexity O(n \times aim)O(n) × Aim), spatial complexity On.

Example 1

Input:

[5,2,3],20

Return value:

4

Example 2

Input:

[5,2,3],0

Return value:

0

Example 3

Input:

[3,5],2

Return value:

-1

remarks

0≤n≤1000
0≤aim≤5000

Solution: dynamic programming

public static int minMoney(int[] arr, int aim) {
  int max = aim + 1;  //Define a global variable
  int[] dp = new int[aim + 1];  //dp[i] means the minimum number of coins when the target value is I
  Arrays.fill(dp, max);  //All dp arrays are defined as maximum values
  dp[0] = 0;
  for (int i = 0; i <= aim; i++) {  //Traversal target value
    for (int j = 0; j < arr.length; j++) {  //Traverse coins
      if (arr[j] <= i) {  //If the current coin is smaller than the target value, it can be exchanged
        dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);
      }
    }
  }
  return dp[aim] > aim ? -1 : dp[aim];
}

knapsack problem

describe

It is known that the maximum volume that a backpack can hold objects is V

There are N items. The volume of the ith item is Vi and the weight is Wi

What is the maximum weight of the current backpack?

Data range:

Example 1

Input:

10,2,[[1,3],[10,4]]

Return value:

4

explain:

The first article has a volume of 1 and a weight of 3, and the second article has a volume of 10 and a weight of 4. Only the second item can reach the optimal scheme, and the weight of the item is 4   

Solution: dynamic programming

For each item, we can only choose to take it or not. We can't choose to load part of an item or load the same item multiple times.

**Solution: * * declare a two-dimensional array with the size of dp[n][V]. dp[i][j] represents the maximum value that can be obtained when facing the ith item and the backpack capacity is j. then we can easily analyze the calculation method of dp[i][j]
(1) When J < w [i], the backpack capacity is insufficient to put down the i-th item, so you can only choose not to take DP [i] [J] = DP [I-1] [J]
(2) In the case of J > = w [i], when the backpack capacity can put down the ith item, we should consider whether we can get greater value with this item.

• If you take it, DP [i] [J] = DP [i-1] [j-w[i] + v [i]. DP [i-1] [j-w[i]] here refers to the maximum value when i-1 items are considered and the backpack capacity is j-w[i], which is also equivalent to making room for w[i] for the ith item.
• If not, DP [i] [J] = DP [I-1] [J], the same as (1)

Whether to take or not, it is natural to compare the two cases, which is of the greatest value.

The state transition equation can be obtained

if(j>=w[i])
    dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
else
    dp[i][j]=dp[i-1][j];

According to the meaning of the question:

public static int knapsack(int V, int n, int[][] vw) {
  if (V == 0 || n == 0 || vw == null) {
    return 0;
  }
  int[][] dp = new int[n + 1][V + 1];
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= V; j++) {
      if (j < vw[i - 1][0]) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);
      }
    }
  }
  return dp[n][V];
}

Longest non repeating subarray

describe

Given an array arr, returns the length of the longest non repeating element subarray of arr. non repeating means that all numbers are different.

The subarray is continuous. For example, the subarray of [1,3,5,7,9] has [1,3], [3,5,7], etc., but [1,3,7] is not a subarray

Example 1

Input:

[2,3,4,5]

Return value:

4

explain:

[2,3,4,5]Is the longest subarray    

Example 2

Input:

[2,2,3,4,3]

Return value:

3

explain:

[2,3,4]Is the longest subarray    

Example 3

Input:

[9]

Return value:

1

Example 4

Input:

[1,2,3,1,2,3,2,2]

Return value:

3

explain:

The longest subarray is[1,2,3]   

Example 5

Input:

[2,2,3,4,8,99,3]

Return value:

5

explain:

The longest subarray is[2,3,4,8,99] 

Solution 1: double pointer + backtracking (improved dynamic programming)

  public static int maxLength1(int[] arr) {
    int tmp = 0, res = 0;
    for (int right = 0; right < arr.length; right++) {
      int left = right - 1;
      while (left >= 0 && arr[left] != arr[right]) {
        left--;
      }
      tmp = tmp < right - left ? tmp + 1 : right - left;
      res = Math.max(res, tmp);
    }
    return res;
  }

• Time: O(n*n)
• Space: O(1)

Solution 2: sliding window

public static int maxLength(int[] arr) {
  if (arr.length < 2) {
    return arr.length;
  }
  HashMap<Integer, Integer> map = new HashMap<>();
  int res = 0;
  int left = -1;
  for (int right = 0; right < arr.length; right++) {
    if (map.containsKey(arr[right])) {
      left = Math.max(left, map.get(arr[right]));
    }
    res = Math.max(res, right - left);
    map.put(arr[right], right);
  }
  return res;
}

• Time: O(n) n is the length of the array
• Space: O(n) n is the length of HashMap.

Longest common substring

describe

Given two strings str1 and str2, the longest common substring of the two strings is output

The topic ensures that the longest common substring of str1 and str2 exists and is unique.

Example 1

Input:

"1AB2345CD","12345EF"

Return value:

"2345"

Solution: dynamic programming

For the strings str1 (length m) and STR2 (length n), we can use a two-dimensional integer array (m * n) to implement the dynamic programming algorithm.

Idea:
dp[i][j]: represents the length of the longest common substring between the substring ending with coordinate I in str1 and the substring ending with coordinate J in str2 (pushed forward from the position of I and j)

Recurrence equation:

• If the i-th character of str1 is not equal to the j-th character of str2, dp[i][j] = 0
• Otherwise dp[i][j] = dp[i-1]d[j-1] + 1

About string interception:
Use an integer variable maxLength to record the length of the current longest common substring
Use an integer variable lastIndex to point to the subscript of the last character of the current longest common substring in str1

public static String LCS(String str1, String str2) {
  int m = str1.length();
  int n = str2.length();
  int[][] dp = new int[m][n];
  int maxLength = 0;
  int lastIndex = 0;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      if (str1.charAt(i) == str2.charAt(j)) {
        if (i == 0 || j == 0) {
          dp[i][j] = 1;
        } else {
          dp[i][j] = dp[i - 1][j - 1] + 1;
        }
        if (dp[i][j] > maxLength) {
          maxLength = dp[i][j];
          lastIndex = i;
        }
      }
    }
  }
  return str1.substring(lastIndex - maxLength + 1, lastIndex + 1);
}