# 到達目的地的最低初始點 > 原文： [https://www.geeksforgeeks.org/minimum-positive-points-to-reach-destination/](https://www.geeksforgeeks.org/minimum-positive-points-to-reach-destination/) 給定一個網格，每個網格由正，負或無點組成，即零點。 僅當我們有正點（> 0）時，我們才能跨單元格移動。 每當我們經過一個像元時，該像元中的點都會添加到我們的總體點中。 我們需要找到從（0，0）到達像元（m-1，n-1）的最小初始點。 限制條件： * 從一個單元（i，j），我們可以移至（i + 1，j）或（i，j + 1）。 * 如果您在（i，j）的總點是< = 0，我們將無法從（i，j）移開。 * 我們必須達到（n-1，m-1）的最小正數點，即> 0。 **示例**： ``` Input: points[m][n] = { {-2, -3, 3}, {-5, -10, 1}, {10, 30, -5} }; Output: 7 Explanation: 7 is the minimum value to reach destination with positive throughout the path. Below is the path. (0,0) -> (0,1) -> (0,2) -> (1, 2) -> (2, 2) We start from (0, 0) with 7, we reach(0, 1) with 5, (0, 2) with 2, (1, 2) with 5, (2, 2) with and finally we have 1 point (we needed greater than 0 points at the end). ``` [](https://practice.geeksforgeeks.org/problem-page.php?pid=91) ## 強烈建議您在繼續解決方案之前，單擊此處進行練習。 乍一看，這個問題看起來與[最大/最小成本路徑](https://www.geeksforgeeks.org/dynamic-programming-set-6-min-cost-path/)類似，但獲得的最大總積分將不能保證最低的初始積分。 另外，在當前問題中必須強制這些點永遠不會降至零或以下。 例如，假設存在從源到目標單元格的兩條路徑。 我們可以通過自下而上的表格填充動態編程技術來解決此問題。 * 首先，我們應維護一個與網格大小相同的 2D 數組 dp，其中 dp [i] [j]代表最小點，可確保進入單元格（i，j）之前繼續到達目的地的旅程。 但很明顯 dp [0] [0]是我們的最終解決方案。 因此，對于此問題，我們需要從右下角到左上角填充表格。 * 現在，讓我們確定離開像元（i，j）所需的最低點（記住，我們正在從底部向上移動）。 只有兩條路徑可供選擇：（i + 1，j）和（i，j + 1）。 當然，我們將選擇玩家可以以較小的初始點完成其余旅程的單元。 因此，我們有： **min_Points_on_exit = min（dp [i + 1] [j]，dp [i] [j + 1]）** 現在我們知道了如何計算 min_Points_on_exit，但是我們需要填充表 dp [] []以獲得 dp [0] [0]中的解。 **如何計算 dp [i] [j]？** dp [i] [j]的值可以寫成如下形式。 dp [i] [j] = max（min_Points_on_exit – points [i] [j]，1） 讓我們看看上面的表達式如何涵蓋所有情況。 * 如果 points [i] [j] == 0，則在該單元格中什么也不會獲得； 玩家離開房間時的點數與進入房間時相同，即 dp [i] [j] = min_Points_on_exit。 * 如果 points [i] [j] <為 0，則玩家必須在進入（i，j）之前獲得大于 min_Points_on_exit 的積分，以補償該單元格中丟失的積分。 最小補償量為“ – points [i] [j]”，因此我們有 dp [i] [j] = min_Points_on_exit – points [i] [j]。 * 如果 points [i] [j] >為 0，則玩家可以進入（i，j）的點數最少為 min_Points_on_exit – points [i] [j]。 因為他可以在該單元格中獲得“ points [i] [j]”分。 但是，在這種情況下，min_Points_on_exit – points [i] [j]的值可能會降至 0 或以下。 發生這種情況時，我們必須將值裁剪為 1，以確保 dp [i] [j]保持正值： dp [i] [j] = max（min_minsPoints_on_exit – points [i] [j]，1 ）。 最后返回 dp [0] [0]，這就是我們的答案。 下面是上述算法的實現。 ## C++ ```cpp // C++ program to find minimum initial points to reach destination #include<bits/stdc++.h> #define R 3 #define C 3 using namespace std; int minInitialPoints(int points[][C]) { ????// dp[i][j] represents the minimum initial points player ????// should have so that when starts with cell(i, j) successfully ????// reaches the destination cell(m-1, n-1) ????int dp[R][C]; ????int m = R, n = C; ????// Base case ????dp[m-1][n-1] = points[m-1][n-1] > 0? 1: ???????????????????abs(points[m-1][n-1]) + 1; ????// Fill last row and last column as base to fill ????// entire table ????for (int i = m-2; i >= 0; i--) ?????????dp[i][n-1] = max(dp[i+1][n-1] - points[i][n-1], 1); ????for (int j = n-2; j >= 0; j--) ?????????dp[m-1][j] = max(dp[m-1][j+1] - points[m-1][j], 1); ????// fill the table in bottom-up fashion ????for (int i=m-2; i>=0; i--) ????{ ????????for (int j=n-2; j>=0; j--) ????????{ ????????????int min_points_on_exit = min(dp[i+1][j], dp[i][j+1]); ????????????dp[i][j] = max(min_points_on_exit - points[i][j], 1); ????????} ?????} ?????return dp[0][0]; } // Driver Program int main() { ????int points[R][C] = { {-2,-3,3}, ??????????????????????{-5,-10,1}, ??????????????????????{10,30,-5} ????????????????????}; ????cout << "Minimum Initial Points Required: " ?????????<< minInitialPoints(points); ????return 0; } ```