我正在嘗試解決leetcode.com 上的以下問題
我發現一個資源問了一個類似的問題，但它沒有產生任何合理的東西。
我能夠提出一個遞回回溯解決方案，但是對于一個非常大的矩陣，它在最后 5 個測驗用例中失敗了。我感覺到有一些重復的作業，但不知道是什么。
邏輯的撰寫方式，我正在努力找出
- 我需要記住的
- 如何定制我的邏輯，以便我在每一步都進行優化
任何幫助表示贊賞
class Solution {
private long max = -1;
public int maxProductPath(int[][] grid) {
long mod=1000000007;
int rows = grid.length;
int cols = grid[0].length;
int cp = 1;
pathFinder(grid, rows, cols, cp, rows-1, cols-1);
if(max < 0 ) return -1;
return (int)(max % mod);
}
public void pathFinder(int[][]grid, int rows, int cols, long cp, int r, int c){
if(r >= rows || c >= cols || r < 0 || c < 0){
return;
}
if(r == 0 && c == 0){
this.max = Math.max(cp * grid[r][c] , this.max);
return;
}
pathFinder(grid, rows, cols, cp * grid[r][c], r - 1, c);
pathFinder(grid, rows, cols, cp * grid[r][c], r , c - 1);
}
}
uj5u.com熱心網友回復：
這似乎對經典的右下動態程式有點扭曲。問題是我們需要兩個狀態，因為我們的最大值可以由兩個正數或兩個負數構成。一般來說：
if grid[i][j] < 0:
dp[i][j][positive] = grid[i][j]
* min(
dp[i-1][j][negative],
dp[i][j-1][negative]
)
dp[i][j][negative] = grid[i][j]
* max(
dp[i-1][j][positive],
dp[i][j-1][positive]
)
if grid[i][j] > 0:
dp[i][j][positive] = grid[i][j]
* max(
dp[i-1][j][positive],
dp[i][j-1][positive]
)
dp[i][j][negative] = grid[i][j]
* min(
dp[i-1][j][negative],
dp[i][j-1][negative]
)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498193.html
上一篇：在圖中查找所有連接的組件及其大小