Skip to main content

CSES Dynamic Programming Problem Solution+Explanation

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

Popular posts from this blog

Create a socket for HTTP for web page upload and download

Create a socket for HTTP for web page upload and download. Aim: To write a java program for socket for HTTP for web page upload and download . Algorithm 1.Start the program. 2.Get the frame size from the user 3.To create the frame based on the user request. 4.To send frames to server from the client side. 5.If your frames reach the server it will send ACK signal to client otherwise it will send NACK signal to client. 6.Stop the program Program : Client import javax.swing.*; import java.net.*; import java.awt.image.*; import javax.imageio.*; import java.io.*; import java.awt.image.BufferedImage; import java.io.ByteArrayOutputStream; import java.io.File; import java.io.IOException; import javax.imageio.ImageIO; public class Client{ public static void main(String args[]) throws Exception{ Socket soc; BufferedImage img = null; soc=new Socket("localhost",4000); System.out.println("Client is running. ");  try { System.out.println("Reading image from disk. "); im...

Write a code simulating ARP /RARP protocols

   Write a code simulating ARP /RARP protocols . Aim:        To write a java program for simulating ARP/RARP protocols ALGORITHM: server 1. Create a server socket and bind it to port. 2. Listen for new connection and when a connection arrives, accept it. 3. Send server ‟ s date and time to the client. 4. Read client ‟ s IP address sent by the client. 5. Display the client details. 6. Repeat steps 2-5 until the server is terminated. 7. Close all streams. 8. Close the server socket. 9. Stop. Client 1. Create a client socket and connect it to the server ‟ s port number. 2. Retrieve its own IP address using built-in function. 3. Send its address to the server. 4. Display the date & time sent by the server. 5. Close the input and output streams. 6. Close the client socket. 7. Stop. Program Program for Address Resolutuion Protocol (ARP) using TCP Client: import java.io.*; import java.net.*; impor...

Write program to find ε – closure of all states of any given NFA with ε transition.

 Write program to find ε – closure of all states of any given NFA with ε transition. Agenda 1.Program 2.Input/Output 1.Program #include <stdio.h> #include <string.h> char  result[ 20 ][ 20 ], copy[ 3 ], states[ 20 ][ 20 ]; void  add_state( char  a[ 3 ],  int  i) {   strcpy(result[i], a); } void  display( int  n) {    int  k =  0 ;   printf( "nnn Epsilon closure of %s = { " , copy);    while  (k < n) {     printf( " %s" , result[k]);     k++;   }   printf( " } nnn" ); } int  main() {   FILE * INPUT;   INPUT = fopen( "input.dat" ,  "r" );    char  state[ 3 ];    int  end, i =  0 , n, k =  0 ;  ...