Introduction to dynamic planning I, BFS of queue (70.121.279.200)

What is dynamic programming

         Dynamic planning is to use historical data to avoid double counting , Historical data is saved in one-dimensional array or two-dimensional array .

Using dynamic programming to solve problems requires two basic steps ：1. First define the array and clarify the meaning of the array , Assign initial value to array ,2. Then find the connection between the elements （ Dynamic transfer equation ） Finally, the result .

Example

Next, use three examples to get started with dynamic planning .

1. climb stairs

1. Define an array dp[ n ],dp[ n ] The value of represents walking to n There are several ways to order .

2. Assign initial value to , obviously dp[ 1 ] = 1, dp[ 2 ] = 2.

3. Look for connections between elements （ Dynamic transfer equation ）, Easy to come by n>=3 After a dp [ n ] = dp[ n - 1 ] + dp[ n - 2 ]; Because I came to n Order can be determined by n - 1 Take one step at a time to reach , It can also be done by n - 2 Take two steps at a time to arrive .

int climbStairs(int n){
    if(n == 1)return 1;
    if(n == 2)return 2;
    int dp[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];
}

2. The best time to buy and sell stocks

         This question is more suitable for traversing an array at one time , Record historical data changes with two variables , Use variables min Record until n God , The lowest selling price of the stock . Reuse gap Record with n Sell stocks at a price of days , The profits you can get , use tgap Record the maximum profit . to min,gap,tgap Assign initial value to 0, After traversing the array once tgap The stored data is the maximum profit .

#define max(a, b) a>b ? a : b
#define min(a, b) a<b ? a : b
int maxProfit(int* prices, int pricesSize){
    int m = prices[0], gap = 0, tgap = 0;
    for(int i = 0; i < pricesSize; i++){
        m = min(m, prices[i]);
        if(prices[i] > m){
            gap = prices[i] - m;
            tgap = max(gap, tgap);
        }
    }
    return tgap;
}

3. Complete square

1. Define an array dp[ n ], dp[ n ] The value of and is expressed as n The minimum number of complete squares of .

2. Assign initial value to , Give Way dp[ n ] = n（ The worst , The factor is n individual 1）.

3. Look for connections between elements （ Dynamic transfer equation ）, Observe to get , There is an optimal connection between two continuous data , for example dp[ 5 ] = 2, that dp[ 6 ] It can be understood as dp[ 5 ]+dp[ 1 ] = 2 + 1 = 4. explain n The optimal solution of is related to the previous data . The connection between the two solutions is j*j, enumeration j = 1;j * j < i; j++; Yes dp[ i ]  = min(dp[ i ], dp[ i - j * j ] + 1);

#define min(a, b) a<b ? a : b
int numSquares(int n){
    int dp[n + 1];
    for(int i = 0; i <= n; i++){
        dp[i] = i;
        for(int j = 1; j * j <= i; j++){
            dp[i] = min(dp[i], dp[i - j * j] + 1);
        }
    }
    return dp[n];
}

Queued bfs

Number of Islands

- How to solve the problem ： Sinking method , Every time a piece of land is found, the whole piece is sunk （ become 0）.

- Specific ideas ： Traversing a two-dimensional array , Find out 1 Back entry bfs, Sink the whole land in the function .

- skill ：1. Create an array of directions dir[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}} Find out 1 when ,for Cycle for four times to judge whether there is land in the upper, lower, left and right of this land , Others are listed .

           2. Use Circular queue ,front The pointer is in front of rear Pointer after , For each front, Judge whether there is land up, down, left and right , One sank the land and then joined the team in this position （ Each cycle rear May move forward 0~3 position ）, After joining the team front Move forward one bit , Repeat the above steps until front == rear The whole land .

int dir[4][2] = {
   {0, 1}, {1, 0}, {0, -1}, {-1, 0}};

typedef struct{
	int x;
	int y;
}node;

#define MAX 305

bool inside(int i, int j, int row, int col){
	return (i >= 0)&&(j >= 0)&&(i < row)&&(j < col);
}

void bfs(char** grid, int i, int j, int gridSize, int colSize){
	node* queue[MAX + 1];
	node* cur = (node*)malloc(sizeof(node));
	cur->x = i;
	cur->y = j;
	int front = 0, rear = 0;
	queue[rear++] = cur;
	while(front != rear){
		cur = queue[front];
		front = (front + 1) % MAX;
		for(int k = 0; k < 4; k++){
			int ox = cur->x + dir[k][0];
			int oy = cur->y + dir[k][1];
			if(inside(ox, oy, gridSize, colSize) && grid[ox][oy] == '1'){
				grid[ox][oy] = '0';
				node* next = (node*)malloc(sizeof(node));
				next->x = ox;
				next->y = oy;
				queue[rear] = next;
				rear = (rear + 1) % MAX; 
			}
		}
	}
}

int numIslands(char** grid, int gridSize, int* gridColSize){
	int colSize = gridColSize[0], ans = 0;
	for(int i = 0; i < gridSize; i++){
		for(int j = 0; j < colSize; j++){
			if(grid[i][j] == '1'){
				ans++;
				bfs(grid, i, j, gridSize, colSize);
			}
		}	
	}
    return ans;
}