The key of dynamic programming is to define the meaning of DP array and write the state transition equation. As long as these two steps are completed, the dynamic programming problem is basically solved. Dp is the abbreviation of Dynamic Programming in DP array.

Let’s first look at a classic dynamic programming problem, which is basically an introduction to dynamic programming, is the famous Fibonacci number;

1. Leetcode 509– Fibonacci number

Fibonacci numbers, usually denoted by F(n), form a sequence called the Fibonacci sequence. The sequence starts with 0 and 1, and each successive digit is the sum of the preceding two. So F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2), where n > 1 gives you n, please calculate F(n).

Example 1: Input: 2 Output: 1 Description: F(2) = F(1) + F(0) = 1 + 0 = 1 Example 2: Input: 3 Output: 2 Description: F(3) = F(2) + F(1) = 1 + 1 = 2Copy the code

Fibonacci number should be the simplest dynamic programming problem, because Fibonacci number definition has listed the state transition method, we directly define dp array to represent the Fibonacci number, and then convert the definition into the state transition equation to solve;

Public int fib(int n) {if (n == 0) {return 0; } if (n == 1) { return 1; } int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }Copy the code

Leetcode 70– Take the stairs

Suppose you’re climbing stairs. It takes n steps to get to the top.

You can climb one or two steps at a time. How many different ways can you climb to the top?

Note: given n is a positive integer.

Example 1: Input: 2 Output: 2 Description: There are two ways to climb to the top of the building. 1. Level 1 + Level 2. Level 2 Example 2: Input: 3 Output: 3 Description: There are three ways to climb to the top of the building. 1. 1 order + 1 order + 1 order 2. 1 order + 2 order 3Copy the code

The solution of the problem is shown below. The definition of dp array is: dp[I] represents the number of methods to climb the I step; Dp [I] = dp[I – 1] + dp[I – 2] They say you can climb one or two steps at a time, so the way you can climb the I step is the sum of the way you can climb the I-1 step and the way you can climb the I-2 step;

Public int climbStairs(int n) {if (n == 1) {return; dp[I] == 1 public int climbStairs(int n) {return 1; } int[] dp = new int[n + 1]; dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }Copy the code

3. Leetcode 300– the longest increasing subsequence

Given an integer array nums, find the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from an array that deletes (or does not delete) the elements of the array without changing the order of the rest of the elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1: input: nums = [10,9,2,5,3,7,101,18] output: 4 explanation: the longest increasing subsequence is [2,3,7,101], so length is 4.Copy the code

Define the meaning of dp array as shown below: Dp [I] represents the length of the longest increasing subsequence ending with nums[I]. According to the definition of dp array, we can solve the state transition equation. First, the for loop iterates through the array of numbers, and when it reaches an element, it compares the element with all elements before it. So they can form an increasing subsequence, and what we do is we take the maximum between the current dp[I] and the previous element j dp[j]+1;

So once we’ve iterated through the entire array, we can get all the values of dp array, and by the definition of dp array, we just iterate through dp array once, taking the maximum value of dp array;

Public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length]; Arrays.fill(dp, 1); for (int i = 0; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } int res = 1; for (int i = 0; i < dp.length; i++) { res = Math.max(res, dp[i]); } return res; }Copy the code

Leetcode 1143– the longest common subsequence

Given two strings text1 and text2, return the length of the longest common subsequence of the two strings. If no common subsequence exists, return 0.

A subsequence of a string is a new string made up of the original string without changing the relative order of the characters by deleting some characters (or none).

For example, “ace” is a subsequence of “ABCDE”, but “AEC” is not a subsequence of “ABCDE”. A common subsequence of two strings is a subsequence that is shared by both strings.

Example 1: Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace", which has length 3. Example 2: Input: text1 = "ABC ", text2 =" ABC "Output: 3 Explanation: The longest common subsequence is" ABC ", which has length 3. Example 3: Input: text1 = "ABC ", text2 = "def" Output: 0 Explanation: The two strings have no common subsequence, return 0.Copy the code

The solution of the problem is as follows. For such a problem of two strings or two arrays, it is generally necessary to define a two-dimensional DP array. Dp [I][j] represents the length of the longest common subsequence of text1[0…i-1] and Text2 [0…j-1]. According to the definition of the dp array, dp[text1.length()][text2.length()] is the desired result;

Dp [I][j] = dp[i-1][J-1] + 1; dp[I] = dp[i-1][j-1] + 1; dp[I] = dp[i-1][j-1] + 1; Otherwise the dp [I] [j] = math.h Max (dp [j], [I – 1] dp [I] [1]). Dp [text1.length()][text2.length()]];

//dp[I][j] indicates the length of the longest subsequence of text1[0...i-1] and Text2 [0...j-1] public int longestCommonSubsequence(String) text1, String text2) { if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) { return 0; } int[][] dp = new int[text1.length() + 1][text2.length() + 1]; for (int i = 1; i <= text1.length(); i++) { for (int j = 1; j <= text2.length(); j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[text1.length()][text2.length()]; }Copy the code

5. Leetcode 516– longest sequence of subrons

Given a string s, find the longest sequence of subroutines and return the length of the sequence. We can assume that the maximum length of s is 1000.

Example 1: Input: "bbbab" Output: 4 The longest possible subroutine sequence is "BBBB". Example 2: Input: "CBBD" Output: 2 One of the longest possible subroutines is "bb".Copy the code

Solution 1: define dp array to solve directly

Dp [I][j] represents the length of the longest subsequence of the subarray s[I…j];

The value of dp[I][j] depends on the value of three positions of DP [I +1][J-1] dp[I +1][j] dp[I][j], so it needs to be traversed from the back to the front. When we draw the two-dimensional number group of DP, the value of DP [I][j] needs to be derived from the bottom left, left and bottom three positions. So the for loop traverses I for rows from n-2 to 0; J is for columns, from I + 1 to n; When s.c harAt (I) = = s.c harAt (j), dp [I] [j] = dp + 1] [I] [j – 1 + 2; Otherwise dp [I] [j] = math.h Max (dp [1], [I] dp [j] [I + 1]).

According to the definition of dp array, the last return dp[0][n-1] can be;

Public int longestPalindromeSubseq(String s) {if (s == null || s.length() == 0) { return 0; } int n = s.length(); int[][] dp = new int[n][n]; //base case for (int i = 0; i < n; i++) { dp[i][i] = 1; } / / dp [j] [I] value depends on dp + 1] [I] [j - 1 dp [j] [I + 1] dp [I] [1] the value of the three locations therefore need from backward traversal for (int I = n - 2; i >= 0; i--) { for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { dp[i][j] = dp[i + 1][j - 1] + 2; } else { dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]); } } } return dp[0][n - 1]; }Copy the code

Solution 2: use the longest common subsequence to solve

First, with the help of StringBilder, the reverse sequence of the desired string is obtained. Then, the longest common subsequence of the original string and the reverse string is obtained. The longest common subsequence is the result.

// LeetCode 516, Public int longestPalindromeSubseq2(String s) {StringBuilder Builder = new StringBuilder(); for (int i = s.length()-1; i >= 0 ; i--) { builder.append(s.charAt(i)); } String resverseText = builder.toString(); return longestCommonSubsequence(s,resverseText); } dp[I][j] indicates the length of text1[0...i-1] and Text2 [0...j-1] public int longestCommonSubsequence(String)  text1, String text2) { if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) { return 0; } int[][] dp = new int[text1.length() + 1][text2.length() + 1]; for (int i = 1; i <= text1.length(); i++) { for (int j = 1; j <= text2.length(); j++) { if (text1.charAt(i - 1) == text2.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[text1.length()][text2.length()]; }Copy the code

6, Leetcode 53– Find the sum of the largest subarray

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.

Example 1: input: nums = [-2,1,-3,4,-1,2,1,-5,4] output: 6 explanation: the maximum sum of consecutive subarrays [4,-1,2,1] is 6. Example 2: Input: nums = [1] Output: 1Copy the code

Open a double nested for loop and make the index of the second loop start with I +1. Each loop adds a number to the index and then compares it to the maximum value. But the time complexity of the algorithm is O(n^2); It’s a little inefficient;

Solution 1: Violence algorithm

Public int maxSubArray(int[] nums) {int res = integer.min_value; for (int i = 0; i < nums.length; i++) { int temp = nums[i]; res = Math.max(res, temp); for (int j = i + 1; j < nums.length; j++) { temp = temp + nums[j]; res = Math.max(res, temp); } } return res; }Copy the code

Solution 2 dynamic programming is as follows, define dp array: dp[I] represents the largest subarray sum ending in NUMs [I]

After defining the meaning of dp array, we iterate over the array of numbers in the for loop. Dp [I] takes the maximum value between nums[I] and nums[I] + dp[i-1]. Dp [I] = nums[I]; dp[I] = nums[I]; Finally, iterate through the DP array to find the maximum value;

Solution 2: Dynamic programming

/ / leetcode 53 for the architectural array and / / dp [I] said to nums [I] for the ending of the architectural array and public int maxSubArray (int [] nums) {if (nums = = null | | nums. Length == 0) { return 0; } int[] dp = new int[nums.length]; // the largest subarray sum of the first element is itself dp[0] = nums[0]; for (int i = 1; i < nums.length; i++) { dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]); } int res = Integer.MIN_VALUE; for (int i = 0; i < dp.length; i++) { res = Math.max(res, dp[i]); } return res; }Copy the code

Leetcode 718– Longest repeating subarray

Given two integer arrays A and B, return the length of the longest common subarray of the two arrays.

Example: Input: A: [1,2,3,2,1] B: [3,2,1,4,7] Output: 3 Explanation: The longest common subarray is [3,2,1].Copy the code

Dp [I][j] represents the length of the longest repeating subarray of the two subarrays ending with nums1[i-1] and nums2[J-1]. We can do this by analogy with the longest common subsequence; If nums1[i-1] == nums2[j-1], dp[I][j] = dp[i-1][j-1] + 1; if nums1[i-1] == nums2[j-1], dp[I][j] = dp[i-1][j-1] + 1;

Finally, open a double nested for loop to get the maximum value of the two-dimensional array dp;

/ / leetcode longest repeated subarray / 718 / dp [I] [j] said to nums1 and nums2 [I - 1] [1] for the end of the two longest subarray repeat the length of the subarray public int findLength (int [] nums1, int[] nums2) { if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) { return 0; } int[][] dp = new int[nums1.length + 1][nums2.length + 1]; for (int i = 1; i <= nums1.length; i++) { for (int j = 1; j <= nums2.length; j++) { if (nums1[i - 1] == nums2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } } } int res = 0; for (int i = 0; i <= nums1.length; i++) { for (int j = 0; j <= nums2.length; j++) { res = Math.max(res, dp[i][j]); } } return res; }Copy the code

8. 0-1 backpack problem

0-1 knapsack problem is a typical dynamic programming problem, 0-1 knapsack problem has many variations, here we discuss the most basic 0-1 knapsack;

The backpack capacity (weight) is W, the item type is N(there is only one item for each item), the weight of all items is the weight array, and the corresponding value is the value array; Weight. length = value.length = N;

What is the maximum value that the backpack can carry?

In fact, the DP array for the 0-1 knapsack problem is extremely difficult to define and extremely difficult to understand; Dp array definition: dp[I][w] indicates that for the first I items, the current backpack capacity is W, in this case, the maximum value can be held is DP [I][w];

Open a double nested for loop, the outer layer circulates the item, the inner layer circulates the backpack capacity, when traverses the item I, the backpack only has two states, either has the capacity to hold the item I, or has no capacity to hold the item I; Dp [I][w] = dp[i-1][w] = dp[i-1][w] = dp[i-1] Dp [I][w] = math.max (dp[i-1][w], dp[i-1][W-weight [i-1]] + value[i-1]) if the current item is large enough to hold, then dp[I][w] = math.max (dp[i-1][W], DP [i-1][W-weight [i-1]] + value[i-1]).

// Knapsack capacity (can carry weight) is W, item type is N(each item has only one), all item weight is the weight array, Dp [I][w] indicates that for the first I items, the current backpack capacity is W, Dp [I][w] public int knapsack(int w, int N, int[] weight, int[] value) { int[][] dp = new int[N + 1][W + 1]; for (int i = 1; i <= N; i++) { for (int w = 1; w <= W; W++) {if (w-weight [i-1] < 0) {// if (w-weight [i-1] < 0) {dp[I][w] = dp[i-1][w]; } else {//dp[I] indicates the ith item, but I is counted from 1, Dp [I][w] = Math. Max (dp[i-1][w], dp[i-1][w-weight [i-1]] + value[i-1]); } } } return dp[N][W]; }Copy the code

Source:

Source: LeetCode link: leetcode-cn.com/problemset/…