DP

 

DP My understanding

 

Recursive dp approach:

When to use?

-when question asks to maximize or minimize a value.

-when we can see if at are at position i we can use value of i+1 or i-1 to form an answer (overlapping problem)

How to use:

At each position index decide answer by max (choose (index), not choose (index));
1. If choosing index, which is the next index we jump to? Call the same function on that index after finding it after adding relevant value at this index.

2. If Not choosing I, move to next index.

If by choosing this index we effect the option for all upcoming indexes then we need to introduce a state and for memorization we use the state.

Questions: Buy stock 2 and 3

Avoid additional states if can be avoided.

if whether current index can be chosen or not is independent of other indexes then we can decided to only choose/not choose or both based on information but if current index decides whether you can choose coming indexes or not then state has to be introduced. (Questions: Buy stock 2 and 3

state for buy stock 2: if stock is bought at day i then for  coming days it cannot be bought, it can only be sold so a state is introduced which tells if current stock can be bought or not, it is reflected in dp memotization.)

state for buy stock 3: if stock is bought at day i then for  coming days it cannot be bought, it can only be sold so a state is introduced also total number of transactions can be made is K which tells stock cannot be bought and sold  more than k times this is the third state, it is reflected in dp memotization.)

If above can be avoided by using different approach like for example in Maximum profit in job scheduling, we use current index and we find the next index we can jump to using the available information. Instead of deciding whether current value can be choosen or not for every index.

The decision should be consistent for every index if possible without states, or with introduction of state can be inconsistent.

maximum-profit-in-job-scheduling

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

States: maximum value achieved till index (single dimension)

Solution:

maximum-number-of-events-that-can-be-attended-ii

You are given an array of events where events[i] = [startDayi, endDayi, valuei]. The ith event starts at startDayi and ends at endDayi, and if you attend this event, you will receive a value of valuei. You are also given an integer k which represents the maximum number of events you can attend.

You can only attend one event at a time. If you choose to attend an event, you must attend the entire event. Note that the end day is inclusive: that is, you cannot attend two events where one of them starts and the other ends on the same day.

Return the maximum sum of values that you can receive by attending events.

States: maximum achieved till I if J elements are selected two dimension.

Solution:


Comments

Post a Comment

Popular posts from this blog

LeetCode 3Sum

Question Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets. Brute force We can run 3 loops to check each possible triplets, we also need to eliminate the duplicates from both sides. this method will work but will work but will give time limit exceed after time constraints. To do this in given time limit we need to sort the array first and Create a loop that fixes the left most integer. This reduces the problem to 2sum for remaining array. For each loop iteration where duplicates are skipped, we need to do a left/right iteration using while loop. my code:
Read more

30. Substring with Concatenation of All Words

Problem Statement You are given a string s and an array of strings words. All the strings of words are of the same length. A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated. For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words. Return the starting indices of all the concatenated substrings in s. You can return the answer in any order. Example 1: Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6. The substring starting at 0 is "barfoo". It is the concaten...
Read more

Lowest common ancestor in a binary Tree

Approach Define a recursive function rec that takes three parameters: root (the current node), p (first node to find the lowest common ancestor for), and q (second node to find the lowest common ancestor for). Check if the current node root is null or if it is either p or q . If any of these conditions is true, return the current node root as the lowest common ancestor. Recursively call the rec function for the left subtree of the current node and assign the result to a variable l . Recursively call the rec function for the right subtree of the current node and assign the result to a variable r . Check if both l and r are not null. If so, it means that p and q are found on different subtrees of the current node, and the current node root is their lowest common ancestor. Return the current node root . If l is null, it means that both p and q are on the right subtree (or not present in the tree). Return r . If none of the above conditions are met, it means ...
Read more