1246. Palindrome Removal

LeetCode hard original: C# #array #csharp #dynamic-programming #hard #leetcode #math #recursion #string

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

Вам дан số nguyên mảng arr. За один ход вы можете выбрать палиндромный подmảng arr[i], arr[i + 1], ..., arr[j], где i <= j, и удалить этот подmảng из данного mảngа. Обратите внимание, что после удаления подmảngа elementы слева и справа от него перемещаются, чтобы заполнить пробел, образовавшийся в результате удаления. return минимальное количество ходов, необходимое для удаления всех чисел из mảngа.

Ví dụ:

Input: arr = [1,2]

Output: 2

C# lời giải

đã khớp/gốc

using System;
public class Solution {
    public int MinMovesToDelete(int[] arr) {
        int n = arr.Length;
        int[,] dp = new int[n, n];
        for (int i = 0; i < n; i++) {
            dp[i, i] = 1;
        }
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (arr[i] == arr[j]) {
                    dp[i, j] = length > 2 ? dp[i + 1, j - 1] : 1;
                } else {
                    dp[i, j] = int.MaxValue;
                    for (int k = i; k < j; k++) {
                        dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k + 1, j]);
                    }
                }
            }
        }
        return dp[0, n - 1];
    }
}

C++ lời giải

bản nháp tự động, xem lại trước khi gửi

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinMovesToDelete(vector<int>& arr) {
        int n = arr.size();
        int[,] dp = new int[n, n];
        for (int i = 0; i < n; i++) {
            dp[i, i] = 1;
        }
        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (arr[i] == arr[j]) {
                    dp[i, j] = length > 2 ? dp[i + 1, j - 1] : 1;
                } else {
                    dp[i, j] = int.MaxValue;
                    for (int k = i; k < j; k++) {
                        dp[i, j] = min(dp[i, j], dp[i, k] + dp[k + 1, j]);
                    }
                }
            }
        }
        return dp[0, n - 1];
    }
}

Java lời giải

đã khớp/gốc

public class Solution {
    public int minMovesToDelete(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (arr[i] == arr[j]) {
                    dp[i][j] = length > 2 ? dp[i + 1][j - 1] : 1;
                } else {
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int k = i; k < j; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }

        return dp[0][n - 1];
    }
}

JavaScript lời giải

đã khớp/gốc

var minMovesToDelete = function(arr) {
    const n = arr.length;
    const dp = Array.from({ length: n }, () => Array(n).fill(0));

    for (let i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    for (let length = 2; length <= n; length++) {
        for (let i = 0; i <= n - length; i++) {
            const j = i + length - 1;
            if (arr[i] === arr[j]) {
                dp[i][j] = length > 2 ? dp[i + 1][j - 1] : 1;
            } else {
                dp[i][j] = Infinity;
                for (let k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
            }
        }
    }

    return dp[0][n - 1];
};

Python lời giải

đã khớp/gốc

def min_moves_to_delete(arr):
    n = len(arr)
    dp = [[0] * n for _ in range(n)]

    for i in range(n):
        dp[i][i] = 1

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if arr[i] == arr[j]:
                dp[i][j] = dp[i + 1][j - 1] if length > 2 else 1
            else:
                dp[i][j] = float('inf')
                for k in range(i, j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])

    return dp[0][n - 1]

Go lời giải

đã khớp/gốc

package main

import (
    "fmt"
    "math"
)

func minMovesToDelete(arr []int) int {
    n := len(arr)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][i] = 1
    }

    for length := 2; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            if arr[i] == arr[j] {
                if length > 2 {
                    dp[i][j] = dp[i+1][j-1]
                } else {
                    dp[i][j] = 1
                }
            } else {
                dp[i][j] = math.MaxInt32
                for k := i; k < j; k++ {
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])
                }
            }
        }
    }
    return dp[0][n-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Algorithm

1⃣Базовый случай:

Если подmảng состоит из одного elementа, то его удаление займет 1 ход, поэтому dp[i][i] = 1.

2⃣Рекурсивный случай:

Если arr[i] == arr[j], то мы можем удалить их в одном ходе, если подmảng arr[i+1...j-1] можно удалить за dp[i+1][j-1] ходов, тогда dp[i][j] = dp[i+1][j-1] (если удалим подmảng arr[i+1...j-1] и затем удалим arr[i] и arr[j]).

3⃣В противном случае, минимальное количество ходов для удаления подmảngа arr[i...j] будет равно 1 + минимум ходов для удаления каждого из подmảngов arr[i...k] и arr[k+1...j], где i <= k < j. То есть, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех k от i до j-1.

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.