Solving the dynamic programming problems

• Dynamic programming is a very important algorithm, and mastery of it should be the basic skills for computer science students.

• Let’s explain as much as possible about the understanding of this type of algorithm.

• The key is `state definition` and `state transition equation`

#### Longest Increasing Subsequence

Given a sequence of K integers { N1, N2, …, NK }, any contiguous subsequence can be expressed as { Ni, Ni+1, …, Nj }, where 1 <= i <= j < = K. The largest contiguous subsequence is the element and the largest one of all consecutive subsequences, such as the given sequence { -2, 11, -4, 13, -5, -2 }, whose largest contiguous subsequence is { 11, -4, 13 } and the maximum sum is 20.

• Define `sum[i]` as the `maximum value of contiguous subsequence with A[i] as the last end`

• The state transition equation is: `sum[i]=max(sum[i-1]+a[i], a[i])`
• T he actual solution is, as long as sum>0, then adding a[i] is still possible to increase max; but if sum<0, it should be discarded immediately, starting from 0 to calculate the next

#### Number tower problem From the top layer to the bottom layer, each layer can only go to the adjacent node, and calculate the sum of the numbers

• Define the state equation: `max[i,j]` represents the sum of the largest numbers passed by [i,j] as the starting point. Then `max[1,1]` is our target

• Define the state transition equation: `max[i,j]=num[i,j]+max(max(i+1,j),max(i+1,j+1))`

• Then you can choose to solve it from top to bottom or from bottom to top

#### Backpack Problem

• There are different versions of backpack problem.Let me illustrate the basic one.

There are N items and a backpack with a capacity of V. The cost of the i-th item is c[i] and the value is w[i]. Decide which items are loaded into the backpack so the sum of the values can be max.

• Solve it with Java.There are two types of answer,see the comment.

### 303 Range Sum Quwey - Immutable

• About the meaning：Give an array that returns the value of any two range of ranges

• Idea: The rpblem content says `many calls to function`, so the traversal solution will definitely be TLE（Time Limit Exceeded); and `sum[i,j]=sum[j]-sum[i-1]` is obvious, so all the sums are found in one pass. After the value is done, subtraction is fine. Note you may need to use global variables

• code:

Writen in Python：

##### 70 climbStatirs

• About the meaning：Ascend a staircase, you can take 1 step or take two steps.if you go to n steps, how many solutions will you have?

• Idea: Use dp[n] to indicate the number of methods to go to n steps. For dp[n-1], you can only choose to take 1 step; for dp[n-2], If you choose 1+1, it will overlap with dp[n-1], you can only choose 2 steps.

• Code：

##### 64 Minimum Path Sum
• About the meaning: `m*n` is a matrix of all positive numbers, which can be moved downwards to the right,find the sum of the distances from the upper left to the lower right.
• Idea: Dynamic programming.using dp[i][j] to represent the shortest number of steps taken with i, j as the last square. Then `dp[i][j]=max(dp[i-1][j]+grid[i][j],dp[i][j-1]+gird[i][j]`,we just need to implement the equation.