Author: Vipul Jain
Tester: Abhishek Mishra
Editorial: Utkarsh Jaiswal
Difficulty:
Medium
Prerequisite:
Array , DP
Explanation & Algorithm:
Given a integer n and three matrix arr1[][] ,arr2[][],arr3[][] which contain the value of x,y and z for each cell respectively, write a function that returns the minimum cost to reach (m, n) from (0, 0.The total cost of a path to reach (m, n) is the sum of all the costs on that path . You can only traverse down, right and diagonally lower cells from a given cell, i.e., from a given cell (i, j), cells (i+1, j), (i, j+1), and (i+1, j+1) can be traversed.
For example, in the following figure, what is the minimum cost path to (2, 2)?
3
1 2 1
3 4 5
1 1 1
2 3 4
1 3 1
2 1 1
1 8 9
1 4 5
6 5 4
The path with minimum cost is (0, 0) - > (1, 0) - >(2, 1) - > (2, 2) .Cost of path is 2 + 1 + 1 is equal to 4.
Optimal sub-problem:
The path to reach (m, n) must be through one of the 3 cells: (m-1, n-1) or (m-1, n) or (m, n-1).
If you reach (m, n) from (m-1,n-1) then total cost will be the cost of to reach (m-1, n-1) plus arr3[m-1, n-1].let this value be stored in variable a.
if you reach (m, n) from (m,n-1) then total cost will be the cost of to reach (m, n-1) plus arr1[m, n-1].let this value be stored in variable b.
If you reach (m, n) from (m-1,n) then total cost will be the cost of to reach (m-1, n) plus arr2[m-1, n].let this value be stored in variable c.
minCost(m, n) =min(min (a, b) , c) .
Approach:
If you solve this recursively then it will take exponential time and it shows the time limit exceeded error.
In the optimal approach we use a temporary matrix dp[][] in which at any cell (i, j) dp[I][j] store the minimum cost to reach (i, j) cell from (0, 0).
Below is the implementation of the approach.
Solution
Setter's Code
#include<bits/stdc++.h>
using namespace std;
int solve(int n,vector<vector> &arr1,vector<vector> &arr2,vector<vector> &arr3){
int dp[n][n]={};
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==0 && j==0){
dp[0][0]=0;
}
else if(i==0){
dp[i][j]=dp[i][j-1]+arr1[i][j-1];
}
else if(j==0){
dp[i][j]=dp[i-1][j]+arr2[i-1][j];
}
else{
int a=dp[i-1][j]+arr2[i-1][j];
int b=dp[i][j-1]+arr1[i][j-1];
int c=dp[i-1][j-1]+arr3[i-1][j-1];
dp[i][j]=min(min(a,b),c);
}
}
}
return dp[n-1][n-1];
}
int main(){
int n;
cin>>n;
vector<vector<int>> arr1(n,vector<int>(n));
vector<vector<int>> arr2(n,vector<int>(n));
vector<vector<int>> arr3(n,vector<int>(n));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>arr1[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>arr2[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>arr3[i][j];
}
}
cout<<solve(n,arr1,arr2,arr3)<<endl;
return 0;
}
Tester's Code
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
void solve() {
ll n; cin >> n;
vector<vector> x(n, vector(n)), y(n, vector(n)), z(n, vector(n)), dp(n, vector(n, 0));
for (auto &r : x) {
for (auto &c : r) cin >> c;
}
for (auto &r : y) {
for (auto &c : r) cin >> c;
}
for (auto &r : z) {
for (auto &c : r) cin >> c;
}
for (ll j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + x[0][j - 1];
}
for (ll i = 1; i < n; i++) {
dp[i][0] = dp[i - 1][0] + y[i - 1][0];
}
dp[0][0] = 0;
for (ll i = 1; i < n; i++) {
for (ll j = 1; j < n; j++) {
dp[i][j] = min({dp[i - 1][j] + y[i - 1][j], dp[i][j - 1] + x[i][j - 1], dp[i - 1][j - 1] + z[i - 1][j - 1]});
}
}
cout << dp[n - 1][n - 1] << "\n";
}
int main() {
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
int tc = 1;
while (tc--) {
solve();
}
return 0;
}