# [leetcode] 动态规划（Ⅱ）

08/13 16:24

{1314, 221, 1277, 877, 96, 64, 120}
Interview - {47}


## 矩阵区域和

class Solution
{
public:
int rows, cols;
vector<vector<int>> matrixBlockSum(vector<vector<int>> &mat, int k)
{
rows = mat.size();
cols = mat[0].size();
vector<vector<int>> prefix(rows, vector<int>(cols, 0));
prefix[0][0] = mat[0][0];
// calculate prefix sum
for (int j = 1; j < cols; j++)
prefix[0][j] = mat[0][j] + prefix[0][j - 1];
for (int i = 1; i < rows; i++)
prefix[i][0] = mat[i][0] + prefix[i - 1][0];
for (int i = 1; i < rows; i++)
for (int j = 1; j < cols; j++)
prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] -
prefix[i - 1][j - 1] + mat[i][j];

vector<vector<int>> ans(rows, vector<int>(cols, 0));
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
ans[i][j] = getval(i + k, j + k, prefix) - getval(i - k - 1, j + k, prefix) -
getval(i + k, j - k - 1, prefix) +
getval(i - k - 1, j - k - 1, prefix);
}
}
return ans;
}

int getval(int x, int y, vector<vector<int>> &prefix)
{
if (x < 0 || y < 0)
return 0;
else
return prefix[min(x, rows - 1)][min(y, cols - 1)];
}
};


## 最大正方形

dp[i,j] = matrix[i, j]                                   if i==0 or j==0
= 0                                              if i>=1 and j>=1 and matrix[i, j]==0
= 1 + min(dp[i, j-1], dp[i-1, j], dp[i-1, j-1])  if i>=1 and j>=1 and matrix[i, j]==1


class Solution
{
public:
int maximalSquare(vector<vector<char>> &matrix)
{
if (matrix.size() == 0)
return 0;
int rows = matrix.size();
int cols = matrix[0].size();
int maxval = 0;
vector<vector<int>> dp(rows, vector<int>(cols, 0));
for (int j = 0; j < cols; j++)
dp[0][j] = (matrix[0][j] == '1'), maxval = max(maxval, dp[0][j]);
for (int i = 0; i < rows; i++)
dp[i][0] = (matrix[i][0] == '1'), maxval = max(maxval, dp[i][0]);
for (int i = 1; i < rows; i++)
{
for (int j = 1; j < cols; j++)
{
if (matrix[i][j] == '1')
dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
else
dp[i][j] = 0;
maxval = max(maxval, dp[i][j]);
}
}
return maxval * maxval;
}
};


## 统计全为 1 的正方形子矩阵

• m[i, j] 为右下角的最大正方形的边长（即上一题的含义）
• m[i, j] 为右下角的正方形的个数（即本题的含义）。为什么会具有这个含义呢？回想上一题的过程，在计算某个位置的 DP 值时，我们以该位置为起点，在其左上方一圈一圈地扩大正方形的范围（直至边界遇到 0 值），所以 dp[i, j] = k 表示的是有 k 个以 m[i, j] 为右下角的正方形，且边长分别为 1, 2, ..., k ，如下图所示。

class Solution
{
public:
int countSquares(vector<vector<int>> &matrix)
{
if (matrix.size() == 0 || matrix[0].size() == 0)
return 0;
int rows = matrix.size();
int cols = matrix[0].size();
vector<vector<int>> dp(matrix);
int sum = 0;
for (int i = 1; i < rows; i++)
{
for (int j = 1; j < cols; j++)
{
if (matrix[i][j] == 1)
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
else
dp[i][j] = 0;
sum += dp[i][j];
}
}
for (int i = 0; i < rows; i++)  sum += dp[i][0];
for (int j = 1; j < cols; j++)  sum += dp[0][j];
return sum;
}
};


int spaceOptimize(vector<vector<int>> &matrix)
{
if (matrix.size() == 0 || matrix[0].size() == 0)
return 0;
int rows = matrix.size();
int cols = matrix[0].size();
int sum = 0;
vector<int> pre(matrix[0]);
vector<int> cur(cols, 0);
for (int i = 1; i < rows; i++)
{
cur[0] = matrix[i][0];
for (int j = 1; j < cols; j++)
{
if (matrix[i][j] == 1)  cur[j] = 1 + min(cur[j - 1], min(pre[j], pre[j - 1]));
else  cur[j] = 0;
sum += cur[j];
}
pre = cur;
}
for (int j = 0; j < cols; j++)  sum += matrix[0][j];
for (int i = 1; i < rows; i++)  sum += matrix[i][0];
return sum;
}


## 石子游戏

**答案是先手必胜。**这里有偶数堆石头，石头的总和是奇数，每个人只能取头尾的二者之一。所以，必然有一方取得所有的奇数堆，一方取得所有的偶数堆（从 1 开始计数）。并且 Sum(奇数堆) 和 Sum(偶数堆) 必然是一大一小的（因为总和是一个奇数）。

return true 即可。

## 礼物的最大价值

dp[i,j] = dp[0,j-1] + grid[0,j]                 if i==0
= dp[i-1,0] + grid[i,0]                 if j==0
= max(dp[i-1,j], dp[i,j-1]) + grid[i,j] if i>=1 and j>=1


class Solution
{
public:
int maxValue(vector<vector<int>> &grid)
{
if (grid.size() == 0 || grid[0].size() == 0)
return 0;
int rows = grid.size();
int cols = grid[0].size();
vector<vector<int>> dp(rows, vector<int>(cols, 0));
dp[0][0] = grid[0][0];
for (int j = 1; j < cols; j++)  dp[0][j] = dp[0][j - 1] + grid[0][j];
for (int i = 1; i < rows; i++)  dp[i][0] = dp[i - 1][0] + grid[i][0];
for (int i = 1; i < rows; i++)
for (int j = 1; j < cols; j++)
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
return dp.back().back();
}
};


## 最小路径和

class Solution
{
public:
int minPathSum(vector<vector<int>> &grid)
{
if (grid.size() == 0 || grid[0].size() == 0)
return 0;
int rows = grid.size();
int cols = grid[0].size();
// some trick to simplify the code
vector<vector<int>> dp(rows + 1, vector<int>(cols + 1, 0x3f3f3f3f));
dp[0][1] = dp[1][0] = 0;
for (int i = 1; i <= rows; i++)
for (int j = 1; j <= cols; j++)
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
return dp[rows][cols];
}
};


## 三角形最小路径和

class Solution
{
public:
int minimumTotal(vector<vector<int>> &triangle)
{
if (triangle.size() == 0 || triangle[0].size() == 0)
return 0;
vector<vector<int>> dp(triangle);
int minval = 0x3f3f3f3f;
for (int i = 1; i < dp.size(); i++)
for (int j = 0; j < dp[i].size(); j++)
dp[i][j] = min(getval(j-1, dp[i - 1]), getval(j, dp[i - 1])) + triangle[i][j];
auto &v = dp.back();
for (int x : v)
minval = min(minval, x);
return minval;
}

int getval(int x, vector<int> &v)
{
int len = v.size();
if (0 <= x && x < len)  return v[x];
return 0x3f3f3f3f;
}
};


## 不同的二叉搜索树

h(n)= \left\{ \begin{aligned} & 0, & n=0 \\ & n, & n=1, 2 \\ & \sum_{i=0}^{n-1}h(i)h(n-i-1), & n\ge3 \end{aligned} \right.

$$h(n)$$ 是具有 n 个节点，不同的二叉搜索树的数目（条件也可以是二叉树？），任意选定一个根节点，那么剩余的 $$n-1$$ 个节点需要分配到左右子树。假如左子树 $$a$$ 个节点，右子树 $$n-1-a$$ 个节点，那么选定某个根的情况下产生的数目为 $$h(a)*h(n-1-a)$$

$h(n) = h(n-1) \cdot \frac{4n-2}{n+1}, n=0,1,2,...$

class Solution
{
public:
int numTrees(int n)
{
return dp(n);
}
int dp(int n)
{
if (n <= 2)  return n;
vector<int> catalan(n + 1, 0);
catalan[0] = catalan[1] = 1, catalan[2] = 2;
for (int i = 3; i <= n; i++)
for (int k = 0; k < i; k++)
catalan[i] += catalan[k] * catalan[i - k - 1];
return catalan.back();
}
int func(int n)
{
uint64_t h = 1;
for (int i = 1; i <= n; i++)
h = h * 2 * (2 * i - 1) / (i + 1);
return h;
}
};


0
0 收藏

0 评论
0 收藏
0