1246. Palindrome Removal

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

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

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

Exemple:

Input: arr = [1,2]

Output: 2

C# solution

correspondant/original

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++ solution

brouillon automatique, à relire avant soumission

#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 solution

correspondant/original

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 solution

correspondant/original

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 solution

correspondant/original

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 solution

correspondant/original

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⃣Базовый случай:

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

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

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

3⃣В противном случае, минимальное количество ходов для удаления подtableauа arr[i...j] будет равно 1 + минимум ходов для удаления каждого из подtableauов 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

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.