某动态规划小题

好像是谷歌面试题…中比较弱智的

  • 输入: 一个m*n矩阵ary, 矩阵元素只有0和1
  • 输出: 寻找从左上到右下的连续路径中最长的路径长度(也就是只能往右或往下或往右下走)
  • 定义: 只要1的周围8个点有1就定义为连续路径
  1. 状态矩阵定义: $dp[i][j]$代表在$ary[:i][:j]$子矩阵中, 经过点$arr[i][j]$的路径的最大值
  2. 状态转移方程:
    $$ dp[i][j] = \begin{cases} max \lbrace & dp[i-1][j], \\
    & dp[i][j-1], \\
    & dp[i-1][j-1] \rbrace + 1, & ary[i][j] = 1 \\
    0, && ary[i][j] = 0
    \end{cases}$$
  3. 首先计算出dp第一行第一列的值, 再从左向右从上到下计算整个dp数组, 最后统计最大值即可
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:
int dp_sol(vector<vector<int> > & ary)
{
int max_route = 0;
auto m = ary.size();
auto n = ary[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
// init 1st row
for (int i = 0; i < n; ++i) {
if (ary[0][i] == 1) {
if ((i != 0) && (ary[0][i-1] == 1)) {
dp[0][i] = dp[0][i-1] + 1;
} else {dp[0][i] = 1;}
}
}
// init 1st col
for (int i = 0; i < m; ++i) {
if (ary[i][0] == 1) {
if ((i != 0) && (ary[i-1][0] == 1)) {
dp[i][0] = dp[i-1][0] + 1;
} else {dp[i][0] = 1;}
}
}
// dp
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (ary[i][j] == 1) {
dp[i][j] = max(max(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
}
}
}
// find max
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (dp[i][j] > max_route) {max_route = dp[i][j];}
}
}
return max_route;
}
};
int main() {
vector< vector<int> >
a = {{0, 1, 1, 0},
{1, 0, 0, 0},
{1, 0, 1, 0},
{1, 0, 0, 1}};
Solution s = Solution();
cout<<s.dp_sol(a)<<endl;
return 0;
}

拓展:
如果允许往任意方向走, 那就成了一个搜索最大的连通分量的题