# Java solution, DP

• ``````class Solution {
public int strangePrinter(String s) {
int n = s.length();
if (n == 0) return 0;

int[][] dp = new int[101][101];
for (int i = 0; i < n; i++) dp[i][i] = 1;

for (int i = 1; i < n; i++) {
for (int j = 0; j < n - i; j++) {
dp[j][j + i] = i + 1;
for (int k = j + 1; k <= j + i; k++) {
int temp = dp[j][k - 1] + dp[k][j + i];
if (s.charAt(k - 1) == s.charAt(j + i)) temp--;
dp[j][j + i] = Math.min(dp[j][j + i], temp);
}
}
}
return dp[0][n - 1];
}
}
``````

• @shawngao said in Java solution, DP:

for (int i = 0; i < n; i++) dp[i][i] = 1;

``````    for (int i = 1; i < n; i++) {
for (int j = 0; j < n - i; j++) {
dp[j][j + i] = i + 1;
for (int k = j + 1; k <= j + i; k++) {
int temp = dp[j][k - 1] + dp[k][j + i];
if (s.charAt(k - 1) == s.charAt(j + i)) temp--;
dp[j][j + i] = Math.min(dp[j][j + i], temp);
}
}
}
return dp[0][n - 1];
``````

Can you explain why the 2D array is trying to calculate?
I am trying to solve with recursion but I can start from front or back but can't find a way to start from middle.

• I removed some redundant dp[j][k - 1] + dp[k][j + i] ops as we only need to check-and-merge left-hand side with every occurrence of the same character on the right (correct me if I'm wrong).

``````#define forn(i,n) for(int i = 0; i < (n); i++)
class Solution {
public:
int strangePrinter(string s) {
int dp[101][101], N = s.size();
if(N <= 1) return N;
forn(i, N) dp[i][i] = 1;
for(int i = N-2; i >= 0; i--){
for(int j = i+1; j < N; j++){
dp[i][j] = dp[i+1][j] + 1;
char c = s[i];
for(int k = i; k < j; k++){
if(s[k+1] == c) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]-1);
}
}
}
return dp[0][N-1];
}
};
``````

• @zaw_moe so as some posters wrote, it's quite similar to the remove boxes question (#546), the 2D arrays holds the minimum number of printings needed between letters `[i...j]`.

• @shawngao This might be the best answer. However, can you explain what 'k' stands for or, in other words: how can you prove the optimal sub_structure?

• @baselRus Thank you. I am now running the code to understand the if checking in the K loop.

• @zhangsikai123
what the algorithms doing is

1. it sets basic print to 1 per character
2.it sets [i][i] to 1, which means any substring start from i to i (basically a single char).
2. it add 1 to the printing needs as soon as there is extra char. after [i]loop and [j]loop.
3. then it checks substring between [i] and [j] which is [k]
then it minus the printing needs as soon as it found a same char. (it uses the data from last run so basically it is checking one char per turn)
4. [i] is decreasing. [j] is increasing. which means it is checking from the middle with k running between i and j.
5. it uses the Math.min to check wether [i][j] value (which can be lower if there is alot of character common from start to end) and take the lower value.
6. return the substring [0] [n-1] , i.e. the whole string value back.

When i saw the problem, my instincts told me it is recursive pattern. This is clever execution of recursion into iteration and use keys avoid repetitive calculations.

Thanks everybody for sharing.

• This post is deleted!

• @zaw_moe Tks!

• renamed the variables which may be easier to understand:

``````int strangePrinter(string s) {
// # steps to print s[i, j]
std::vector<std::vector<int>> buffer(s.length(), std::vector<int>(s.length(), 0));
for (int len = 1; len <= s.length(); ++len) {
for (int left = 0; left < s.length() - len + 1; ++left) {
int right = left + len - 1;
buffer[left][right] = len; // print one char at a time
// try print [left, k] && [k+1, right]
for (int k = left; k < right; ++k) {
int steps = buffer[left][k] + buffer[k+1][right];
if (s[left] == s[k+1] || s[k] == s[right]) {
--steps;
}
buffer[left][right] = std::min(buffer[left][right], steps);
}
}
}
return buffer.empty() ? 0 : buffer[0][s.length() - 1];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.