動態規劃解題：最小操作次數使數組變為美麗數組
問題描述
給定一個下標從0開始、長度為n的整數數組nums和一個整數k。你可以對數組中的任意一個元素進行加1操作，操作次數不限。如果數組中任意長度大于或等于3的子數組的最大值都大于或等于k，則稱該數組為美麗數組。我們需要找到使數組變為美麗數組所需的最小操作次數。
問題分析
這個問題的核心是如何通過最少的操作次數，使得數組滿足特定的條件。具體來說，我們需要確保數組中所有長度大于或等于3的子數組的最大值都大于或等于k。為了實現這一目標，我們可以使用動態規劃的方法。
動態規劃思路
動態規劃是一種將復雜問題分解為子問題的算法思想。在這個問題中，我們可以定義一個數組dp[i]，表示將數組nums的前i個元素變成美麗數組所需的最小操作次數。
狀態定義
-
dp[i]：表示將數組nums的前i個元素變成美麗數組所需的最小操作次數。
狀態轉移
對于每個位置i，我們需要考慮以下三種情況：
-
只考慮當前元素：即
nums[i]單獨作為一個子數組的一部分。 -
當前元素與前一個元素一起考慮：即
nums[i]和nums[i-1]作為一個長度為2的子數組的一部分。 -
當前元素與前兩個元素一起考慮：即
nums[i]、nums[i-1]和nums[i-2]作為一個長度為3的子數組。
為了滿足美麗數組的條件，我們需要確保：
-
如果只考慮當前元素，那么
nums[i]必須大于或等于k。 -
如果考慮當前元素與前一個元素，那么
nums[i]和nums[i-1]中至少有一個必須大于或等于k。 -
如果考慮當前元素與前兩個元素，那么
nums[i]、nums[i-1]和nums[i-2]中至少有一個必須大于或等于k。
因此，dp[i]的值應該是：
-
如果
nums[i] >= k，則dp[i] = min(dp[i-1], dp[i-2], dp[i-3])。 -
如果
nums[i] < k，則dp[i] = min(dp[i-1], dp[i-2], dp[i-3]) + (k - nums[i])。
初始化
-
如果數組長度小于3，直接返回0，因為不存在長度大于或等于3的子數組。
-
初始化
dp[0]、dp[1]和dp[2]：-
dp[0] = Math.max(0, k - nums[0])：只考慮第一個元素nums[0]，如果它小于k，則需要k - nums[0]次操作。 -
dp[1] = Math.max(0, k - nums[1])：只考慮第二個元素nums[1]，如果它小于k，則需要k - nums[1]次操作。 -
dp[2] = Math.max(0, k - nums[2])：只考慮第三個元素nums[2]，如果它小于k，則需要k - nums[2]次操作。
-
返回結果
最終返回dp[n-1]、dp[n-2]和dp[n-3]中的最小值。這是因為最后一個元素可能與前兩個元素一起考慮，因此需要選擇最小的操作次數。
代碼實現
以下是Java代碼實現：
class Solution {public long minIncrementOperations(int[] nums, int k) {int n = nums.length;if (n < 3) {return 0; // 如果數組長度小于3，直接返回0}// dp[i]表示將數組nums的前i個元素變成美麗數組所需的最小操作次數long[] dp = new long[n];dp[0] = Math.max(0, k - nums[0]); // 初始化第一個位置dp[1] = Math.max(0, k - nums[1]); // 初始化第二個位置dp[2] = Math.max(0, k - nums[2]); // 初始化第三個位置// 動態規劃計算for (int i = 3; i < n; i++) {// 當前位置需要的操作次數long currentCost = Math.max(0, k - nums[i]);// 選擇最小的操作次數dp[i] = Math.min(dp[i - 1], Math.min(dp[i - 2], dp[i - 3])) + currentCost;}// 返回最后三個位置的最小值return Math.min(dp[n - 1], Math.min(dp[n - 2], dp[n - 3]));}
}示例解析
假設nums = [2, 3, 5, 1, 4]，k = 4。
-
初始化：
-
dp[0] = Math.max(0, 4 - 2) = 2 -
dp[1] = Math.max(0, 4 - 3) = 1 -
dp[2] = Math.max(0, 4 - 5) = 0
-
-
動態規劃計算：
-
i = 3：-
currentCost = Math.max(0, 4 - 1) = 3 -
dp[3] = min(dp[2], dp[1], dp[0]) + currentCost = min(0, 1, 2) + 3 = 3
-
-
i = 4：-
currentCost = Math.max(0, 4 - 4) = 0 -
dp[4] = min(dp[3], dp[2], dp[1]) + currentCost = min(3, 0, 1) + 0 = 0
-
-
-
返回結果：
-
Math.min(dp[4], Math.min(dp[3], dp[2])) = Math.min(0, Math.min(3, 0)) = 0
-
因此，最終結果是0，表示不需要任何操作即可滿足條件。
總結
通過動態規劃，我們可以高效地解決這個問題。動態規劃的關鍵在于：
-
定義合適的狀態
dp[i]。 -
找到狀態轉移方程。
-
初始化邊界條件。
-
返回最終結果。
希望這篇博客能幫助你更好地理解這個問題的解法！如果你有任何疑問或需要進一步的解釋，歡迎留言討論。
)
