 # POORCHF- Editorial

Author: shrabana99
Tester: aman_robotics

EASY.

DP.

# EXPLANATION:

Consider for N = 1, we just need to find minimum cost of the classes on the single day.
For N \geq 2, we fill the table, dp[][] with a high value. Dp[i][k] is the minimum total cost upto i th day if we attend the k th class on that day. So on i th day, for each class k in range (0, M), we calculate minimum total cost (including that class) from minimum total cost of i-1 th day (excluding that class). On nth day, we need to return minimum total cost upto nth day.

# SOLUTIONS:

Setter's Solution

indent whole code by 4 spaces

Tester's Solution
``````import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStream;

/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
PrintWriter out = new PrintWriter(outputStream);
solver.solve(1, in, out);
out.close();
}

long INF = (long) 1e18 + 1;
PrintWriter out;
int n;
int m;
long[][] mat;
long[][] dp;

long go(int ind, int last) {
if (ind == n)
return 0;
if (dp[ind][last] != -1)
return dp[ind][last];
long min = INF;
for (int i = 0; i < m; i++) {
if (i == last)
continue;
min = Math.min(min, go(ind + 1, i) + mat[ind][i]);
}
return dp[ind][last] = min;
}

public void solve(int testNumber, InputReader in, PrintWriter out) {
this.out = out;
this.in = in;
n = ni();
m = ni();
mat = new long[n][m];
dp = new long[n][m];
int i = 0, j = 0;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++)
mat[i][j] = nl();
}
for (i = 0; i < n; i++)
Arrays.fill(dp[i], -1);
long min = INF;
for (i = 0; i < m; i++)
min = Math.min(min, go(1, i) + mat[i]);
pn(min);
}

int ni() {
return in.nextInt();
}

long nl() {
return in.nextLong();
}

void pn(long zx) {
out.println(zx);
}

}

private InputStream stream;
private byte[] buf = new byte;
private int curChar;
private int numChars;

this.stream = stream;
}

if (numChars == -1) {
throw new UnknownError();
}
if (curChar >= numChars) {
curChar = 0;
try {
} catch (IOException e) {
throw new UnknownError();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}

public int nextInt() {
return Integer.parseInt(next());
}

public long nextLong() {
return Long.parseLong(next());
}

public String next() {
while (isSpaceChar(c)) {
}
StringBuffer res = new StringBuffer();
do {
res.appendCodePoint(c);
} while (!isSpaceChar(c));

return res.toString();
}

private boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}

}
}
``````
3 Likes

Setter’s Solution:

``````#include<bits/stdc++.h>

#define ll long long
#define inf 1000000005

using namespace std;

int a, dp;

int main(){

int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> a[i][j];
dp[i][j] = inf;
}

}

for(int j = 0; j < m; j++){
dp[j] = a[j];
}

for(int i = 1; i < n; i++){
for(int j = 0; j < m; j++){
for(int k = 0; k < m; k++){
if(j != k)
dp[i][k] = min(dp[i][k], dp[i-1][j]+a[i][k]);
}
}
}

int ans = inf;
for(int j = 0; j < m; j++){
ans = min(ans, dp[n-1][j]);
}
cout << ans << endl;
}``````