Problem 1-Dice Combinations
Editorial-
Now start from base
1->1
2->1+1,2+0
3->1+1+1,2+1,1+2,3+0
now for-4
we substract from 1 to min(6,4)
( we substract 1 then remaining 3 now we add no.of possible way to constuct 3)+(we substract 2 remaining(4-2=2,no of possible way to constuct 2)+(we substract 3,no. of possible way to construct 1)+(we substract 4 ,now of possible way to construct 0).
i think you got the point
base condition-
dp[0]=1;
how dp[0] ,for this there is empty subset exist
Solution-
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
#define mod 1000000007
ll dp[1000010];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin>>n;
dp[0]=1;
for(int i=1;i<=n;i++)
{
ll ans=0;
for(int j=1;j<=min(6,i);j++)
{
ans+=dp[i-j];
ans%=mod;
}
dp[i]=ans;
}
cout<<dp[n];
}
Problem 2-Minimizing Coins
Editorial-
Parent Problem-Unbounded Knapsack
Let understand through example-
3 11
1 5 7
we have to construct 11 from minimum no of coins from given coin {1,5,7}
minimum coins for 1->1
minimum coins for 2->1+1
minimum coins for 3->min(1 coin of 1+(3-1))->1 coin of 1 +minimum coins for construct 2
we have already calculated minimum coins for 2
dp[3]=1+dp[2-1]
minimum coin for 4->1 coin of 1+minimum coins for construct 3
minimum coins for 5->{1 coins of 1+minimum coins for construct 4} or {1 coin of 5 +minimum coins for construct 0}
and so on.
dp[i]=minimum coin required to constuct i.
base consition-
dp[0]=0
Solution-
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
ll dp[1000010];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,x;
cin>>n>>x;
ll a[n];
for(int i=0;i<n;i++)
cin>>a[i];
dp[0]=0;
for(int i=1;i<=x;i++)
{ dp[i]=INT_MAX;
for(int k=0;k<n;k++)
{ if(a[k]<=i)
{
dp[i]=min(dp[i],1+dp[i-a[k]]);
}
}
}
if(dp[x]==INT_MAX)
cout<<"-1";
else
cout<<dp[x];
}
Problem 3-Coin Combinations I
Editorial-
This is same as Previous in this problem we have to add instead of find minimum
Eg.
3 9
2 3 5
0->1
1->0
2->1 ways{1}
3->{2,ways{1}}+{3,ways{0}}// we already calculated for 1 and 0
4->{2,ways{4-2=2}}+{3,ways{1}}
5->{2,ways{5-2=3}}+{3,ways{5-3=2}}+{5.,ways{0}}
and so on....
base condition dp[0]=1;
Solution-
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
#define mod 1000000007
ll dp[1000010];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,x;
cin>>n>>x;
ll a[n];
for(int i=0;i<n;i++)
cin>>a[i];
dp[0]=1;
for(int i=1;i<=x;i++)
{
for(int j=0;j<n;j++)
{
if(a[j]<=i)
{
dp[i]+=dp[i-a[j]];
dp[i]%=mod;
}
}
// cout<<dp[i]<<" ";
}
cout<<dp[x];
}
Problem 4-Coin Combinations II
Solution-
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
#define mod 1000000007
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,x;
cin>>n>>x;
int a[n];
vector<vector<int>> dp(n+1,vector<int>(x+1,0));
dp[0][0]=1;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
for(int j=0;j<=x;j++)
{ dp[i][j]=dp[i-1][j];
if(a[i-1]<=j)
{
(dp[i][j]+=dp[i][j-a[i-1]])%mod;
dp[i][j]%=mod;
}
}
}
cout<<dp[n][x];
}
Problem 5-Removing Digits
Editorial-
This problem is based on 0-1 knapsack
for example
we remove each digit and take minimum of each case
But there is a deadlock if we substract 0 so avoid 0.
Technique-recursion+memoization
Solution-
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
int dp[1000010];
int solve(int n)
{ if(n<0)
return 1e8;
if(n==0)
return 0;
if(dp[n]!=-1)
return dp[n];
int ans=1e8,p=n;
while(p!=0)
{
ll x=p%10;
p/=10;
if(x!=0)
ans=min(ans,1+solve(n-x));
}
return dp[n]=ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin>>n;
memset(dp,-1,sizeof(dp));
solve(n);
cout<<dp[n];
}
Problem 6-Grid Paths
Editorial-
base case -
row 0-if there is a block then from that block to n=0
column 0-if there is block then from that block 0 to n=0
otherwise if
there is no "#" in left and up then dp[i][j]=dp[i-1][j]+dp[i][j-1]
Solution-
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
#define mod 1000000007
ll dp[1001][1001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin>>n;
string s[n+1];
for(int i=0;i<n;i++)
cin>>s[i];
if(s[0][0]=='*')
dp[0][0]=0;
else
dp[0][0]=1;
for(int i=1;i<n;i++)
{
if(s[i][0]=='*')
dp[i][0]=0;
else
dp[i][0]=dp[i-1][0];
if(s[0][i]=='*')
dp[0][i]=0;
else
dp[0][i]=dp[0][i-1];
}
for(int i=1;i<n;i++)
{
for(int j=1;j<n;j++)
{
if(s[i][j]=='*')
{
dp[i][j]=0;
continue;
}
if(s[i-1][j]==s[i][j-1]&&s[i-1][j]!='*')
dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
dp[i][j]%=mod;
}
}
cout<<dp[n-1][n-1];
}
Problem 7-Book Shop
Editorial-
Based on 0-1 knapsack.
Solution-
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
int main()
{
int n,x;
cin>>n>>x;
vector<int>p(n),v(n);
for(int i=0;i<n;i++)
cin>>p[i];
for(int i=0;i<n;i++)
cin>>v[i];
vector<vector<int>> dp(n+1,vector<int>(x+1,0));
for(int i=1;i<=n;i++)
{
for(int j=0;j<=x;j++)
{
dp[i][j]=dp[i-1][j];
if(j-p[i-1]>=0)
dp[i][j]=max(dp[i][j],v[i-1]+dp[i-1][j-p[i-1]]);
}
}
cout<<dp[n][x];
}
Problem 8-Array Description
Editorial-
For every xi=0 we fill it from 1 to m and check is it valid or not in each step we take prev and pointer i
if prev-xi>1 we return 0
and if i reach n then this will we valid combination so return 1
and sum all these combition will be answer.
Technique- recursion+memoization
Solution-
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
#define mod 1000000007
ll n,m,a[100001];
ll dp[100001][101];
ll solve(ll curr,ll i)
{
if(i==n)
return 1;
if(dp[i][curr]!=-1)
return dp[i][curr];
if(a[i]!=0)
{
if(abs(curr-a[i])>1)
return 0;
else
return solve(a[i],i+1);
}
else
{
ll ans=0;
for(int j=1;j<=m;j++)
{
if(abs(j-curr)<=1)
ans+=solve(j,i+1);
ans%=mod;
}
return dp[i][curr]=ans;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++)
cin>>a[i];
if(a[0]!=0)
cout<<solve(a[0],1);
else
{ ll ans=0;
for(int i=1;i<=m;i++)
{
ans+=solve(i,1);
ans%=mod;
}
cout<<ans;
}
}
Problem 9-Edit Distance
Solution-
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s1,s2;
cin>>s1>>s2;
int n=s1.size(),m=s2.size();
vector<vector<int>> dp(n+1, vector<int>(m+1,1e9));
dp[0][0]=0;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{ if (i) {
dp[i][j] = min(dp[i][j], dp[i-1][j]+1);
}
if (j) {
dp[i][j] = min(dp[i][j], dp[i][j-1]+1);
}
if (i && j) {
dp[i][j] = min(dp[i][j], dp[i-1][j-1]+(s1[i-1] != s2[j-1]));
}
}
}
cout<<dp[n][m];
}
Problem 10-Rectangle Cutting
Editorial-
In each cut we divide into 2
for example
3*4 can be-{3*1+3*3} or {3*2+3*2} or {3*3+3*1}
or
3*4={1*4+2*4} or{2*4+1*4}
squere if i==j
then minimum cut =0;
Solution-
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
ll dp[1000][1000];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{ if(i==j)
dp[i][j]=0;
else
{ dp[i][j]=INT_MAX;
for(int k=1;k<j;k++)
dp[i][j]=min(dp[i][j],(1LL+dp[i][k]+dp[i][j-k]));
for(int k=1;k<i;k++)
dp[i][j]=min(dp[i][j],(1LL+dp[i-k][j]+dp[k][j]));
}
}
}
cout<<dp[n][m];
}
If there is a mistake then tell me i will correct .
Happy Coding.
Comments
Post a Comment