Поток: для каждой проблемы я напишу рекурсивный код, а затем просто формулу dp (в некоторых случаях я бы также написал инициализацию в случае сверху вниз)
// Общие советы
При подходе сверху вниз базовое условие рекурсивного решения преобразуется в инициализацию dp. В мемоизированном решении мы сначала инициализируем dp с -1, а затем, если значение присутствует, мы возвращаем, иначе мы идем и сначала вычисляем первое значение, и очень важно, сохраняем их, а затем возвращаем, чтобы оно было доступно в следующий раз.
Ладно, давайте окунемся в поездку !!!
ПРОБЛЕМЫ С РОДИТЕЛЕМ KNAPSACK 0/1
1. 0/1 KNAPSACK
// проблема
Given an array of weights and its value along with a capacity. We need to find the maximum profit we can get out of it. The below solution is going to form the base for all the problems from 2-7
TC и SC - O (n²)
2. Сумма подмножества (родительская задача: рюкзак 0/1)
// РЕКУРСИВНЫЙ
bool is_subset(int nums[],int sum,int n){
if(sum==0)return true;
if(n==0)return false;
if(nums[n-1]>sum)return is_subset(nums,sum,n-1);
return is_subset(nums,sum-nums[n-1],n-1) || is_subset(nums,sum,n-1)
}
// DP
int dp[n+1][sum+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=sum;j++{
if(j==0)dp[i][j]=1;
else if(i==0)dp[i][j]=0;
else if(nums[i-1]>j)dp[i][j]=dp[i-1][j];
else dp[i][j]= dp[i-1][j] || dp[i-1][j-nums[i-1]];
}
}
// dp[n][sum] contains the answer
3. Задача разделения равной суммы (родитель: сумма подмножества, родительский элемент: рюкзак 0/1)
// проблема
equal sum partition problem says that we need to divide the array into two subsets such that the sum of both the subsets are same.
// сумма = нечетное
if after adding all the elements if the total is odd then we can never divide the array into two parts such that there sum will be equal!
// сходство с суммой подмножества
basically this problem says find if there is a subset such that the sum is (TOTAL/2)!!!!
// код
int total = 0; for(int i=0;i<n;i++)total += nums[i]; if(total%2==1)return false; else apply_subset_sum_with_sum_equal_to_total_divide_by_2
4. Количество подмножеств с заданной суммой (родительский: сумма подмножества, родительский родитель: 0/1 рюкзак)
The subset sum problem asked for true/false hence we did or opeartion, now instead of that we can do addition That is, dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]] And yeah we are good to go!!!
Совет: то же самое происходит, если нам нужно найти количество способов разделить массив на две части, чтобы сумма была одинаковой !!
5. Минимальная разница в сумме подмножества
// постановка задачи
We need to partition the array into two parts such that difference of the sum of the elements of the array is minimum. This questions seems to be misleading and thought provoking but it is indeed very very easy and very very similar to the one which we did previously.
// Идея
Lets consider two subsets say S1 and S2. Now, if Sum(S1)==Sum(S2), then the difference is minimum and we will get 0! In all other cases Sum(S1) < Sum(S2) or Sum(S2) < Sum(S1). What i want to say is that the sum of one of the halfs will be lesser than the others. We also know that Sum(S1)+Sum(S2)=total Suppose that Sum(S1)<Sum(S2)---- (1) Now, Sum(S1) = total - Sum(S2) Now,what will be the possible values of Sum(S1)? maximum value of Sum(S1) will be equal to Sum(S2) and then onwards as the value of Sum(S2) increases the value of Sum(S1) will decrease and will eventually have greater differences in their sums. Hence, finally !!! We can use subset sum target problem here,we can apply the code of target sum of total/2. If the value at that index is false then the first true value from right side will give the value of Sum(S1) that will have the minimum difference!!!!!!! Booom!
// Вариант кода
for(int i=0;i<n;i++)total += nums[i]
int sum = total/2;
for(int i=0;i<=n;i++){
for(int j=0;j<=sum;j++){
if(j==0)dp[i][j]=1;
else if(i==0)dp[i][j]=0;
else if(nums[i]>j)dp[i][j]=dp[i-1][j];
else dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]]
}
}
//Now after doing this we can check
int i;
for(i=sum;i>=0;i--)if(dp[n][i])break;
//Now at this point i will have optimal value
//Hence min diff!!!
return total-i;
Это один из моих любимых вопросов ❤
6. Количество способов разбить массив таким образом, чтобы мы получили минимальную разницу.
Same as number of ways to partition the array into two parts just in this case we will use the above code and instead of or we will use addition!!! So that we will return the value at the element i.e. dp[n][found_min_index]!
7. Целевая сумма со знаком +/-
//постановка задачи
We have been given an array and a target sum. We need to attch a symbol(+/-) before an element such that the resultant of the elements of the array is equal to the target sum. We need to find such number of ways. for e.g. given an array 1 1 2 3 and target sum of 1 ways are 3 +1 +1 +2 -3 +1 -1 -2 +3 -1 +1 -2 +3
// логика
Its like partitioning problem where we can divide the array into two parts such that the difference is of the given element. So, that the rest of the elements can be subtracted and we can get that required sum! Boom we are done! We know that, Sum(S1)-Sum(S2)=e; ---(1) Sum(S1)+Sum(S2)=total; ---(2) Adding 1 and 2 we get, 2*Sum(S1)=e+total therefore, Sum(S1)=(e+total)/2; This tells that if e+total is odd we can direclty return 0; else we will apply subset sum problem to find the number of subsets with sum of the elements value equal to (e+total)/2;
Это финал большинства задач, родительский рюкзак которых равен 0/1 !!!
ЧАСТЬ 2: НЕОГРАНИЧЕННЫЙ РЮКЗАК (РОДИТЕЛЬ)
In unbounded knapsack, multiple occurences of a particualar item is allowed, that is there is infinte supply of given items.
// вариант кода
Поскольку мы можем брать один и тот же элемент любое количество раз, поэтому даже если мы возьмем его один раз, это все еще необработанный bcz, есть вероятность, что мы возьмем этот элемент снова.
// вариант кода в dp
dp[i][i] = dp[i-1][j] || dp[i][j-wt[i-1]]
// рекурсивный подход
int max_profit(int wt[],int val[],int nums[],int n,int w){
if(w<=0 || n==0)return 0;
if(wt[n]>w)return max_profit(wt,val,nums,n-1,w);
return max(max_profit(wt,val,nums,n-1,w),max_profit(wt,val,nums,n,w-wt[n]))
}
8. Проблема с разрезанием стержня
//проблема
We have been given a rod of length n and we have to cut the rod into pieces possibly 0 such that we can maximise the profit. The profit associated with each length is given at profit[i] where it denotes the profit we can gain if we have a cut of length i
// интуиция
we can have as many cuts of given length hence it is an unbounded knapsack problem.
//код
for length=0, the profit we get=0!
hence,
we will create an array of length n which is total length of the rod and we initialize all of them with 0! Since inititially we can get 0 profit with all the lengths.
NOTE:The best part about these problems is that we can solve them in O(N) space.
So,for every i from 1 to n, we will loop through the entire array and dp[j] = max(dp[j],profit[i]+dp[i-j]) //if j>=i else no changes
dp[n] at the last will hold the max profit!
int n;
cin>>n;
int profit[n+1];
for(int i=1;i<=n;i++)cin>>profit[i];
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
dp[j]=max(dp[j],dp[j-i]+profit[i]);
}
}
return dp[n];
// некоторая вариация
Here we have lengths from 1 to n available but instead of that you may have been given an array of length[n] such that length[i] denotes the permissible length of the rod that can be cut! changes in the code, dp[j] = max(dp[j],dp[j-length[i-1]]) //if length[i-1]<j
9. Проблема со сменой монеты (максимальное количество способов)
//постановка задачи
You have been given n denominations which we can use to form a particular value. We have to find the number of ways such that we can reach to that value using the given denominations. NOTE: We can use the denominations any number of times
//код
This is same kinda problem where in number of ways of making 0 is choosing no coin so dp[0]=1 while the rest will be initialized to 0. now for every ith denominaton we have to get the number of ways of making j-den[i-1] value. We can add this value to the current element and we are good to go for finding the number of ways. Hence, dp[j] = dp[j] + dp[j-den[i-1]] // if den[i-1]>=j else dp[j] and dp[n] will give us the number of ways!!!
10. Минимальное количество монет
//постановка задачи
In the previous problem we calculated the number of ways, in this problem we need to find that way which yeild minimum number of coins. Hey, not that way but essentially the minumum number of coins...
// логика
So, if we have no denominations then there are no ways of making that value except value=0(bcz its 1, i.e. no value). Hence, we will relate to previous one... we will initialize the array with INT_MAX for every i>=1 and <=value, for i=0 dp[i]=1; Now, we need minimum coins hence, dp[j] = min(dp[j],dp[j-den[i-1]]+1); // here we are checking if the current coins are minimum or if i include that denomination will give the minimum. // by including i mean 1(that coin)+(minimum ways to find that j-den[i-1])
// небольшой подвох !!!
if you initialize with INT_MAX then 1+INT_MAX = INT_MIN! So,please beware while initilizing.We may initilialize with value+1 bcz thats not possible for any denominations to! only if we have a negative denomination :")
ЧАСТЬ 3: 11. ДОЛГОЕ ОБЩЕЕ ПОСЛЕДОВАТЕЛЬСТВО (РОДИТЕЛЬ) [Тот, у которого максимальное количество потомков] По крайней мере, два массива точно!
//проблема
Finding the length of the longest common subsequence between two the strings
// логика (рекурсивная)
string a,b;
cin>>a>>b;
int n = a.size();
int m = b.size();
int LCS(string a,string b,int n,int m){
if(n==0 || m==0)return 0;
if(a[n-1]==b[m-1])return 1+LCS(a,b,n-1,m-1);
return max(LCS(a,b,n,m-1),LCS(a,b,n-1,m-1));
}
// снова мемоизация
dp [102] [102] // позволяем максимальным ограничениям быть 100 и 100
int dp[102][102];
memset(dp,-1,sizeof(dp));
int LCS(string a,string b,int n,int m){
if(n==0 || m==0)return 0;
if(dp[n][m]!=-1)return dp[n][m];
if(a[n-1]==b[m-1])return dp[n][m]=1+LCS(a,b,n-1,m-1);
return dp[n][m]=max(LCS(a,b,n-1,m),LCS(a,b,n,m-1));
}
//dp
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i==0 || j==0)dp[i][j]=0;
if(a[i]==b[j])dp[i][j]=1+dp[i-1][j-1];
else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
}
}
12. Самая длинная общая подстрока
Here we need to find substring. Now, take the complete analogy from the previous one. There if a[i]!=b[i] we were required to find that do we have more matchings ahead, but in this case we don't have to. Hence, if its not matching then d[i][j]=0, else the same thing!!!!
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i==0 || j==0)dp[i][j]=0;
if(a[i]==b[j])dp[i][j]=1+dp[i-1][j-1];
else dp[i][j]=0; //here is where game chages
}
}
Примечание: чтобы найти его длину, если мы можем найти максимальный элемент в последней строке, а затем вернуться на шаг назад и распечатать его !! (распечатайте его от индекса i-length до length :))
13. Печать LCS
In the first question, we did find the length of lcs but here we are required to print the entire LCS.
// логика
Firstly, make the dp table of lcs
So, we will start with i=n,j=m;
if(a[i]==b[j])it means that the element was taken in lcs to we will add to our lcs...
else if we need to see where we came from, the left side or from top?
So, the one which is greater is what will give us the way..
so, if(dp[i-1][j] > dp[i][j-1])then we came from top else we came from left...
So, the code will be...
//code
int i=n,j=m;
string ans="";
while(i>0||j>0){
if(a[i]==b[j]){ans += a[i];i--;j--;}
else if(dp[i-1][j] > dp[i][j-1])i--;
else j--;
}
ans = ans.reverse();
cout<<ans<<endl;
14. Кратчайшая общая суперпоследовательность
//проблема
This problem says we need to find such a shortest string such that both a and b strings are subsequences of that string. say a = 'yell',b='ylp', the shortest can be 'yellp'
// логика
We can see that both of them will have same characters which are there is the LCS of both the strings.Hence, length of supersequence is LCS + (n - LCS) + (m - LCS) = n+m-LCS
Now,for printing the supersequence we can do the following,
i=n,j=m;
if(a[i]==b[j]){ //if same taking once
ans += a[i];
i--;j--;
}else{
if(dp[i-1][j] > dp[i][j-1]){ //it came from top so for sure b[j] is // not there but top one can match the // previous one
ans += b[j];j--;
}else{ //reverse goes here
ans += a[i];i--;
}
}
printing reverse of ans will give us the supersequence!!!!
15. Минимальное количество вставок и удалений для преобразования строки a в строку b (уменьшенная версия EDIT DISTANCE)
This is the crazy question and completely relates to the previous one!! So we know that we have common elements equal to LCS. Now, the remaining non-matching elements will be L(a)-LCS. Now, all these elements should be deleted right???? And L(b)-LCS will be again uncommon in b...what will we do in this case, we will add right??insert? So, Total deletion+insertions = L(a)-LCS + L(b)-LCS = L(a)+L(b)-2*LCS! Boom!Its done! :) Also,if you know edit distance problem, instead of taking 1+max(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]). Since,here replacement is not there, we can do 1+max(dp[i][j-1],dp[i-1][j])
16. Самая длинная паллиндромная подпоследовательность
//проблема
we need to find the length of the longest pallindromic subsequence.
// логика
This is a really cool problem. So, what we can do is if lets say a[i] == a[j], what we had to do was check whats the length of the longest pallindromic subsequence that can be formed within i+1 and j-1. So, the main idea is to store the length for smaller ranges and then use it for longer ones... for we will start with range=1 and then finally our range will be equal to array length and that is where we will get the longest pallindromic subsequnce length for the entire array.
So,
dp[n+1][n+1];
for(int i=1;i<=n;i++)dp[i][i]=1;
for(int i=2;i<=n;i++){
for(int j=0;j<n-i;j++){
if(a[j]==a[j+i-1])i==2 ? dp[i][j]=2 : dp[i][j]=2+dp[i+1][j-1];
else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
}
}
dp[1][n] will have max value...
17. Самая длинная повторяющаяся подпоследовательность
//вопрос
We need to find a longest sequence which repeats itslef.. for e.g. a a b e b c d d a a b e b c d d The bold letters signify the sequence
// логика
Its like finding the LCS between the same string just that the elements taken in first string should not be taken in second string. i.e. it is same as finding the LCS of string a with string a such that when a[i]==a[j] we should make sure that i!=j and thats it! if(a[i]==a[j] && i!=j )dp[i][j]=dp[i-1][j-1]+1; else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
18. Сопоставление с образцом последовательности
given string a we need to find whether string a is a subsequence of string b! Mind you, this is the only offstring which has O(N) TC
what if we can do is we can start with i=0 pointing to string a and j=0 pointing to string b, if a[i]==b[j] then we can move i ahead, whenever we get same letters, we are good to go ahead... we don't need to think abt it again..
So,
int i=0,j=0;
while(i<n && j<m){
if(a[i]==b[j])i++;
j++
}
if(i==n)return true;
else return false;
19. Минимальное количество вставок / удалений для создания паллиндрома.
Okay so again here we can find LPS, and that is already pallindrome right!? So, rest of elements can either be deleted or its pair can be added... So, minimum number of insertions/deletions = L(s)-L(LPS) Wasn't it great!?
Итак, на этом наша часть 2, родительский элемент LCS подошла к концу ... теперь давайте перейдем к части 3!
3. УМНОЖЕНИЕ МАТРИЧНОЙ ЦЕПИ (РОДИТЕЛЬ)
20. MCM
//проблема
//dp[1001][1001]
//memset(dp,-1,sizeof(dp))
int solve(int a[],int i,int j){
if(i>=j)return 0;
int ans = INT_MAX;
for(int k=i;k<j;k++){
if(dp[i][k]!=-1)dp[i][k]=solve(a,i,k);
if(dp[k+1][j-1]!=-1)dp[k+1][j]=solve(a,k+1,j-1);
int temp_ans = dp[i][k]+dp[k+1][j]+a[i-1]*a[k]*a[j];
ans = min(ans,temp_ans);
}
}
return ans;
4. DP НА ДЕРЕВЬЯХ (РОДИТЕЛЬ)
Скоро выйдет следующая часть… снова плохо редактирую!
