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];
}
}
Java solution, DP


@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 checkandmerge lefthand 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 = N2; 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][N1]; } };

@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 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).  it add 1 to the printing needs as soon as there is extra char. after [i]loop and [j]loop.
 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)  [i] is decreasing. [j] is increasing. which means it is checking from the middle with k running between i and j.
 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.
 return the substring [0] [n1] , 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.
 it sets basic print to 1 per character


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]; }