PROBLEM LINK:
Author: shrabana99
Tester: aman_robotics
DIFFICULTY:
EASY.
PREREQUISITES:
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;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task solver = new Task();
solver.solve(1, in, out);
out.close();
}
static class Task {
long INF = (long) 1e18 + 1;
PrintWriter out;
InputReader in;
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[0][i]);
pn(min);
}
int ni() {
return in.nextInt();
}
long nl() {
return in.nextLong();
}
void pn(long zx) {
out.println(zx);
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1) {
throw new UnknownError();
}
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} 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() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
StringBuffer res = new StringBuffer();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
private boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
}
}