Quy Hoạch Động: tiếng anh là Dynamic Programming, viết tắt là dp

Bài 1: cho 1 dãy số nguyên ~a_{0},a_{0},\dots, a_{n - 1}~ Hãy tìm tổng của dãy con (phải liên tiếp) có tổng lớn nhất:

Test Case #1:

Input = ~-3~ ~20~ ~-214~

Output = ~23~

Cách làm : tạo một mảng ~dp~ gồm ~n~ phần tử (lúc đầu gán hết các phần tử là ~0~), Gọi ~dp_i~ là tổng của dãy con có tổng lớn nhất kết thúc tại index ~i~ => ~dp_0~ ~=~ ~a_0~, duyệt từng index của mảng ~a~ (từ ~1~ -> ~n-1~) gán ~dp_i = \max(a_i,dp_{i - 1} + a_i)~ (vì nó có thể thừa kế từ index ~i-1~, hoặc bắt đầu và kết thúc tại index ~i~), rồi trả ra phần tử lớn nhất của mảng ~dp~ Code bằng python:

a = [int(x) for x in input().split()]
dp = [0 for _ in range(len(a))]
dp[0] = a[0]
for i in range(1,len(a)):
    dp[i] = max(a[i], dp[i-1] + a[i])
print(max(dp))

Bài 2: cho ~1~ dãy số nguyên ~a_0,a_1,\dots,a_{n-1}~ Hãy tìm tổng của dãy con (phải liên tiếp) có tổng nhỏ nhất:

Test Case #1 : Input = ~-3~ ~20~ ~-214~

           Output = ~-214~

Cách làm : tạo một mảng dp gồm n phần tử (lúc đầu gán hết các phần tử là ~0~), Gọi ~dp_i~ là tổng của dãy con có tổng nhỏ nhất kết thúc tại index ~i~ => ~dp_0 = a_0~, duyệt từng index của mảng a (từ ~1~ -> ~n-1~) gán ~dp_i = \min(a_i,dp_{i-1}+a_{i})~ (vì nó có thể thừa kế từ index ~i-1~, hoặc bắt đầu và kết thúc tại index ~i~), rồi trả ra phần tử nhỏ nhất của mảng ~dp~

Code bằng python:

a = [int(x) for x in input().split()]
dp = [0 for _ in range(len(a))]
dp[0] = a[0]
for i in range(1,len(a)):
    dp[i] = min(a[i], dp[i-1] + a[i])
print(min(dp))