Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1246.html

1246. Palindrome Removal

Level

Hard

Description

Given an integer array arr, in one move you can select a palindromic subarray arr[i], arr[i+1], ..., arr[j] where i <= j, and remove that subarray from the given array. Note that after removing a subarray, the elements on the left and on the right of that subarray move to fill the gap left by the removal.

Return the minimum number of moves needed to remove all numbers from the array.

Example 1:

Input: arr = [1,2]

Output: 2

Example 2:

Input: arr = [1,3,4,1,5]

Output: 3

Explanation: Remove [4] then remove [1,3,1] then remove [5].

Constraints:

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= 20

Solution

Use dynamic programming. Create a 2D array dp of arr.length rows and arr.length columns, where dp[i][j] represents the minimum number of moves needed to remove all numbers from arr[i] to arr[j] for i <= j. Initialize dp[i][j] = j - i + 1 for all 0 <= i <= j < arr.length.

For all 1 <= i < arr.length, set dp[i - 1][i] = 1 if arr[i - 1] == arr[i]. Then loop over i from arr.length - 3 to 1 and loop over j from i + 2 to arr.length - 1, and update dp[i][j] as follows. If arr[i] == arr[j], then update dp[i][j] = dp[i + 1][j - 1]. Also, dp[i][j] is the minimum possible value of dp[i][k] + dp[k + 1][j] among all possible values of k such that i <= k < j.

Finally, return dp[0][arr.length - 1].

  • class Solution {
    public int minimumMoves(int[] arr) {
        int length = arr.length;
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            for (int j = i; j < length; j++)
                dp[i][j] = j - i + 1;
        }
        for (int i = 1; i < length; i++) {
            if (arr[i - 1] == arr[i])
                dp[i - 1][i] = 1;
        }
        for (int i = length - 3; i >= 0; i--) {
            for (int j = i + 2; j < length; j++) {
                if (arr[i] == arr[j])
                    dp[i][j] = dp[i + 1][j - 1];
                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][length - 1];
    }
}

  • class Solution {
public:
    int minimumMoves(vector<int>& arr) {
        int n = arr.size();
        int f[n][n];
        memset(f, 0, sizeof f);
        for (int i = 0; i < n; ++i) {
            f[i][i] = 1;
        }
        for (int i = n - 2; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (i + 1 == j) {
                    f[i][j] = arr[i] == arr[j] ? 1 : 2;
                } else {
                    int t = arr[i] == arr[j] ? f[i + 1][j - 1] : 1 << 30;
                    for (int k = i; k < j; ++k) {
                        t = min(t, f[i][k] + f[k + 1][j]);
                    }
                    f[i][j] = t;
                }
            }
        }
        return f[0][n - 1];
    }
};

  • class Solution:
    def minimumMoves(self, arr: List[int]) -> int:
        n = len(arr)
        f = [[0] * n for _ in range(n)]
        for i in range(n):
            f[i][i] = 1
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                if i + 1 == j:
                    f[i][j] = 1 if arr[i] == arr[j] else 2
                else:
                    t = f[i + 1][j - 1] if arr[i] == arr[j] else inf
                    for k in range(i, j):
                        t = min(t, f[i][k] + f[k + 1][j])
                    f[i][j] = t
        return f[0][n - 1]


  • func minimumMoves(arr []int) int {
	n := len(arr)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
		f[i][i] = 1
	}
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			if i+1 == j {
				f[i][j] = 2
				if arr[i] == arr[j] {
					f[i][j] = 1
				}
			} else {
				t := 1 << 30
				if arr[i] == arr[j] {
					t = f[i+1][j-1]
				}
				for k := i; k < j; k++ {
					t = min(t, f[i][k]+f[k+1][j])
				}
				f[i][j] = t
			}
		}
	}
	return f[0][n-1]
}

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

All Problems

All Solutions