Mengajar Pemrograman Anak – Algoritma Pemrograman Dinamis untuk Menghitung Jumlah Pohon Tak Berdekatan Maksimum

Diberikan akar pohon biner, kembalikan jumlah maksimum bilangan bulat yang dapat diperoleh mengingat tidak ada dua bilangan bulat yang dapat menjadi induk yang berdekatan dengan anak.

Kendala
n 100.000 di mana n adalah jumlah node di root
Contoh 1
Memasukkan

    1
   / 
  4   5
 / 
3   2

Keluaran
10
Penjelasan
Kita dapat memilih 3, 2 dan 5. Perhatikan jika kita memilih 4, kita tidak akan dapat memilih 3 dan 2 karena mereka berdekatan.

Jumlah Pohon Tidak Berdekatan Maksimum melalui Rekursi – Algoritma Pemrograman Dinamis Bottom Up Up

Untuk setiap Node Pohon, kami mengembalikan dua nilai, nilai maksimum jika kami mengambil simpul saat ini, atau jika tidak. Kemudian, jika kita tidak mengambil kiri dan kanan, kita dapat mengambil node saat ini, atau jika kita tidak mengambil node saat ini, nilai maksimum dapat dihitung dengan jumlah nilai dari kiri dan kanan – mengambil atau tidak mengambil .

Nilai dihitung secara rekursif – dari daun ke atas ke akar yaitu Algoritma Pemrograman Dinamis Bawah-atas.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maximumNonAdjacentTreeSum(self, root):
        def dfs(root):
            if not root:
                return 0, 0
            takeLeft, notTakeLeft = dfs(root.left)
            takeRight, notTakeRight = dfs(root.right)
            return root.val + notTakeLeft + notTakeRight, 
                   max(takeLeft, notTakeLeft) + max(takeRight, notTakeRight)
        a = dfs(root)
        return max(a[0], a[1])
# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maximumNonAdjacentTreeSum(self, root):
        def dfs(root):
            if not root:
                return 0, 0
            takeLeft, notTakeLeft = dfs(root.left)
            takeRight, notTakeRight = dfs(root.right)
            return root.val + notTakeLeft + notTakeRight, 
                   max(takeLeft, notTakeLeft) + max(takeRight, notTakeRight)
        a = dfs(root)
        return max(a[0], a[1])

Algoritma Pemrograman Dinamis Top Down melalui Rekursi dengan Memoziation untuk Menghitung Jumlah Pohon Non-Berdekatan Maksimum

Kita dapat memecahkan masalah ini melalui Algoritma Pemrograman Dinamis Top Down. Untuk setiap node, jika kita tidak mengambilnya (melewati parameter boolean untuk menunjukkan bahwa kita bermaksud untuk mengambil node ini atau tidak) – Ada empat kombinasi yaitu mengambil kiri dan kanan, mengambil kiri atau kanan, atau tidak ambil sama sekali.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maximumNonAdjacentTreeSum(self, root):
        if root is None:
            return 0
        @cache
        def dfs(root, taken):
            if root is None:
                return 0
            if taken:
                return dfs(root.left, False) + dfs(root.right, False) + root.val
            return max(dfs(root.left, True) + dfs(root.right, True),
                       dfs(root.left, False) + dfs(root.right, False),
                       dfs(root.left, True) + dfs(root.right, False),
                       dfs(root.left, False) + dfs(root.right, True))
        return max(dfs(root, False), dfs(root, True))
# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maximumNonAdjacentTreeSum(self, root):
        if root is None:
            return 0
        @cache
        def dfs(root, taken):
            if root is None:
                return 0
            if taken:
                return dfs(root.left, False) + dfs(root.right, False) + root.val
            return max(dfs(root.left, True) + dfs(root.right, True),
                       dfs(root.left, False) + dfs(root.right, False),
                       dfs(root.left, True) + dfs(root.right, False),
                       dfs(root.left, False) + dfs(root.right, True))
        return max(dfs(root, False), dfs(root, True))

Untuk DP Top Down, kita harus menerapkan memoisasi melalui cache untuk menghindari perhitungan panggilan fungsi duplikat.

–EOF (Blog Komputasi & Teknologi Terbaik) —

Peringkat Bintang GD
Memuat…

538 kata
Postingan terakhir: GoLang: Alat Unik Baris Perintah (Baca dari Keyboard)