Thoughts Of Solving Dynamic Programming Problems
Solving the dynamic programming problems
About DP

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
andstate 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 themaximum value of contiguous subsequence with A[i] as the last end
 The state transition equation is:
sum[i]=max(sum[i1]+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. Thenmax[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 ith 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); andsum[i,j]=sum[j]sum[i1]
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[n1], you can only choose to take 1 step; for dp[n2], If you choose 1+1, it will overlap with dp[n1], 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[i1][j]+grid[i][j],dp[i][j1]+gird[i][j]
,we just need to implement the equation. 
Code: