原题题目

---

---

代码实现（首刷自解）

int maxProductPath(int** grid, int gridSize, int* gridColSize){
    long long dp1[16][16],dp2[16][16],flag = 0,i,j;
    memset(dp1,0,sizeof(dp1));
    memset(dp2,0,sizeof(dp2));
    for(i=0;i<gridSize;i++)
    {
        for(j=0;j<gridColSize[0];j++)
        {
            if(!grid[i][j]) flag = 1;
            if(grid[i][j] < 0)
            {
                if(!i && !j)    
                    dp1[i][j] = grid[i][j];
                else if(!i) 
                {
                    dp1[i][j] = dp2[i][j-1] * grid[i][j];
                    dp2[i][j] = dp1[i][j-1] * grid[i][j];
                }
                else if(!j)
                {
                    dp1[i][j] = dp2[i-1][j] * grid[i][j];
                    dp2[i][j] = dp1[i-1][j] * grid[i][j];
                }
                else
                {
                    dp1[i][j] = fmin(dp2[i-1][j] * grid[i][j],dp2[i][j-1] * grid[i][j]);
                    dp2[i][j] = fmax(dp1[i-1][j] * grid[i][j],dp1[i][j-1] * grid[i][j]);
                }
            }
            else
            {
                if(!i && !j)    
                    dp2[i][j] = grid[i][j];
                else if(!i) 
                {
                    dp1[i][j] = dp1[i][j-1] * grid[i][j];
                    dp2[i][j] = dp2[i][j-1] * grid[i][j];
                }
                else if(!j)
                {
                    dp1[i][j] = dp1[i-1][j] * grid[i][j];
                    dp2[i][j] = dp2[i-1][j] * grid[i][j];
                }
                else
                {
                    dp1[i][j] = fmin(dp1[i][j-1] * grid[i][j],dp1[i-1][j] * grid[i][j]);
                    dp2[i][j] = fmax(dp2[i][j-1] * grid[i][j],dp2[i-1][j] * grid[i][j]);
                }
            }
        }
    }
    if(dp2[gridSize-1][gridColSize[0]-1] <  0 || (!dp2[gridSize-1][gridColSize[0]-1]) && !flag)  return -1;
    else return dp2[gridSize-1][gridColSize[0]-1] % 1000000007;
}

---

---

双百截图