educative.io

Honest bottom-up dynamic programming solution

Courses
,
#1

Hi

Was trying to introduce solution without longest increasing sequence finding.

Please, criticise

    public int findMinimumDeletions(int[] nums) {
    int[] dp = new int[nums.length]; // number of elements to delete to make sequence increasing

    for (int curr = 1; curr < nums.length; ++curr) {
        dp[curr] = curr;
        for (int prev = 0; prev < curr; ++prev) {
            if (nums[curr] >= nums[prev]) {
                dp[curr] = Math.min(dp[curr], dp[prev] + curr - prev - 1);
            } else {
                dp[curr] = Math.min(dp[curr], dp[prev] + curr - prev);
            }
        }
    }

    return dp[nums.length - 1];
}

Course: Grokking Dynamic Programming Patterns for Coding Interviews - Learn Interactively
Lesson: Minimum Deletions to Make a Sequence Sorted - Grokking Dynamic Programming Patterns for Coding Interviews

#2

Ok, I’ve found counterexample, which breaks solution.

It’s [4,8,10,5,6]

Course: Grokking Dynamic Programming Patterns for Coding Interviews - Learn Interactively
Lesson: Minimum Deletions to Make a Sequence Sorted - Grokking Dynamic Programming Patterns for Coding Interviews