資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：計算將列表轉換為非遞增列表所需的運算次數
假設我們有一個名為nums的數字列表。現在讓我們考慮一個操作，我們將兩個連續的值合併成一個值，方法是將它們相加。我們必須找到使列表變為非遞減所需的最小操作次數。
因此，如果輸入類似於nums = [2, 6, 4, 10, 2]，則輸出將為2，因為我們可以將[2, 6]合併得到[8, 4, 10, 2]，然後將[8, 4]合併得到[12, 10, 2]。
為了解決這個問題，我們將遵循以下步驟：
如果nums為空，則
返回0
在nums的末尾插入-∞
N := nums的大小
dp := 一個大小為N的列表，並填充0
arr := 一個大小為N的列表，並填充0
p := arr的大小
arr[p-1] := nums[N-1]
arr[p-2] := nums[N-2]
對於範圍N - 3到0的i，遞減1，執行：
j := i
x := nums[j]
當j < N - 1且x < arr[j + 1]時，執行：
j := j + 1
x := x + nums[j]
dp[i] := j - i + dp[j + 1]
arr[i] := x
返回dp[0]
讓我們看看下面的實現以更好地理解：
示例
class Solution:
def solve(self, nums):
if not nums:
return 0
nums.append(float("−inf"))
N = len(nums)
dp = [0] * N
arr = [0] * N
arr[−1] = nums[−1]
arr[−2] = nums[−2]
for i in range(N − 3, −1, −1):
j = i
x = nums[j]
while j < N − 1 and x < arr[j + 1]:
j += 1
x += nums[j]
dp[i] = j − i + dp[j + 1]
arr[i] = x
return dp[0]
ob = Solution()
nums = [2, 6, 4, 10, 2]
print(ob.solve(nums))輸入
[2, 6, 4, 10, 2]
輸出
2
更新於：2020-12-25
瀏覽量：100
廣告