This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

2. How to solve the problem

1. Dynamic planning

This kind of problem is easy to think about in terms of dynamic programming, and the boundary conditions are easy to understand, but finding the dynamic transfer equation is more challenging. Define dp[][] array, dp[I][j] is the minimum operand of the character interval [I,j].

  • If I ==j, dp[I][j]=1 because there is only one character (boundary condition)

i! How do I compute dp[I][j] when =j? Dp [I][j-1] [j-1]

  • S [I]==s[j], dp[I][j]=dp[I][J-1] In this case, new characters do not affect the printing times.
  • S [J-1]== S [j],dp[I][j]=dp[I][J-1] that is, the new character is the same as the last character. In this case, new characters do not affect the printing times.

Apart from the above two cases that do not affect the number of prints, how should we calculate? We can think of the two parts as the interval [I,k] and the interval [k+1,j] (where I ≤k

  • So instead of starting at 0, the code enumerates I from large to small and enumerates j from small to large, so that dp[I][k] and dp[k+1][j] have been evaluated when dp[I][j] is evaluated.

Time complexity analysis

3 repeats, so the time complexity is:

  • O(n^3)

Spatial complexity analysis

A two-dimensional DP array is required, so the space complexity is:

  • O(n^2)

Three, code implementation

class Solution { public int strangePrinter(String s) { int n = s.length(); int[][] f = new int[n][n]; for (int i = n - 1; i >= 0; i--) { f[i][i] = 1; for (int j = i + 1; j < n; j++) { if (s.charAt(i) == s.charAt(j)) { f[i][j] = f[i][j - 1]; }else if(s.charAt(j-1) == s.charAt(j)){ f[i][j] = f[i][j - 1]; } else { int minn = Integer.MAX_VALUE; for (int k = i; k < j; k++) { minn = Math.min(minn, f[i][k] + f[k + 1][j]); } f[i][j] = minn; } } } return f[0][n - 1]; }}Copy the code

I don’t know if I have made myself clear, please give me more advice. Punch out for the day!