动态规划入门一，队列的bfs（70.121.279.200）

什么是动态规划

        动态规划就是利用历史数据避免重复计算，历史数据用一维数组或二维数组保存。

利用动态规划解题最基本需要经历两个步骤：1.先定义数组并明确数组的意义，给数组赋初值，2.再找到各个元素之间联系（即动态转移方程）最后得出结果。

例题

接下来用三道例题入门动态规划。

1.爬楼梯

1.定义数组dp[ n ]，dp[ n ]的值表示走到n阶有几种方法。

2.赋初值，显然dp[ 1 ] = 1, dp[ 2 ] = 2.

3.寻找元素间的联系（即动态转移方程），容易得出n>=3之后有dp [ n ] = dp[ n - 1 ] + dp[ n - 2 ];因为走到n阶可以由n - 1阶一次走一个台阶到达，也可以是由n - 2阶一次走两个台阶到达。

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.买卖股票的最佳时机

        此题更适合一次遍历数组，用两个变量记录历史数据变化，即用变量min记录截止到第n天，股票的最低售价。再用gap记录用第n天的价格卖出股票，能得到的利润，用tgap记录利润的最大值。给min，gap，tgap赋初值0，一次遍历完数组后tgap存储的数据即为最大利润。

#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.完全平方数

1.定义数组dp[ n ], dp[ n ]的值表示和为n的完全平方数的最少数量。

2.赋初值，让dp[ n ] = n（最坏情况，因子为n个1）。

3.寻找元素间的联系（动态转移方程），观察可得，两个连续数据之间存在最优联系，例如dp[ 5 ] = 2,那么dp[ 6 ]就可以理解为dp[ 5 ]+dp[ 1 ] = 2 + 1 = 4。说明n的最优解与前面的数据有关联。两个解之间的联系为 j*j，枚举j = 1；j * j < i； j++;有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];
}

队列的bfs

岛屿数量

-解题方法：沉没法，每发现一片陆地就把其整片沉没（变成0）。

-具体思路：遍历二维数组，发现1后进入bfs，在函数内把整片陆地沉没。

-技巧：1.创建方向数组dir[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1}}发现1时，for循环四次判断该块陆地的上下左右有无陆地，有则入列。

           2.使用循环队列，front指针在前rear指针在后，对于每个front，判断其上下左右有无陆地，有则沉没该块陆地然后将这个位置入队（每次循环rear可能前移0~3位），入队完成后front前移一位，重复上述步骤直至front == rear整片陆地。

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;
}