Chương trình tìm số phép tăng mảng con tối thiểu để tạo mảng mục tiêu trong Python

Cho mảng target (giá trị dương). Mảng initial cùng kích thước toàn 0. Phép toán: chọn mảng con bất kỳ, tăng mỗi phần tử 1. Tìm số phép tối thiểu để biến initial thành target.

Ví dụ: target = [2,3,4,3,2], đầu ra = 4.

• Bước 1: tăng [0..4] → [1,1,1,1,1]
• Bước 2: tăng [0..4] → [2,2,2,2,2]
• Bước 3: tăng [1..3] → [2,3,3,3,2]
• Bước 4: tăng [2] → [2,3,4,3,2]

Giải pháp

Quan sát: số phép = tổng các lần tăng độ cao khi quét trái sang phải:

• prev_num := 0, steps := 0
• Với mỗi val trong target:
  • steps += val - prev_num nếu val > prev_num, ngược lại 0
  • prev_num := val
• Trả về steps

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

def solve(target):
    prev_num = 0
    steps = 0
    for val in target:
        steps += val - prev_num if val > prev_num else 0
        prev_num = val
    return steps

target = [2,3,4,3,2]
print(solve(target))

Đầu vào

[2,3,4,3,2]

Đầu ra

4