# 1. leetcode topic

## 1.strange printer

topic description

There is a strange printer with the following two special requirements:

- The printer can only print sequences of the same character at a time.
- New characters can be printed at any position from the beginning to the end each time, and the existing characters will be overwritten.
- Given a string s, your task is to calculate the minimum number of prints this printer needs to print it.

## 2. Test cases

enter:

s = "aaabbb"

output:

2

explain:

First print "aaa" and then "bbb".

## 3. Ideas (difficult, I didn’t have an idea at first, I read my own code written in the solution)

Interval DP:

- Because each print must start printing from the first number, so
- when s [ i + j ] ( 0 < j < l e n − i ) s[i+j](0 < j < len-i) s[i+j] (0<j<len−i) and s [ i ] s[i] When s[i] is the same, print s [ i ] s[i] s[i] can be printed casually s [ i + j ] s[i+j] s[i+j], does not require additional printing times.
- s [ i ] ! = s [ j ] s[i] != s[j] s[i]!=s[j], that is, the characters at both ends of the interval are different, then we need to print the left and right parts of the interval separately.

## 4. Algorithm implementation

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

# 2. Blue Bridge Topic

## 1.Xiaoming's backpack 2

topic description

Xiaoming has a capacity of
V
V
V's backpack.

He went shopping in the mall that day, and the mall had a total of N N N items, the th i i The volume of i items is w i w_i wi, the value is v i v_i vi , there are infinitely many of each item.

Xiao Ming wants to know that the total volume of the purchased items does not exceed
V
V
What is the maximum value that can be obtained in the case of V, please help him to calculate.

enter description

Input line 11 contains two positive integers
N
,
V
N,V
N,V, represent the number of items in the mall and the capacity of Xiaoming's backpack.

No. 2 ∼ N + 1 2\sim N+1 2∼N+1 rows contain 2 positive integers w , v w,v w,v, represent the volume and value of the item.

1 ≤ N ≤ 1 0 3 , 1 ≤ V ≤ 1 0 3 ， 1 ≤ w i , v i ≤ 1 0 3 1\leq N\leq10^3, 1≤V≤10^3，1 \leq w_i, v_i \leq 10^3 1≤N≤103,1≤V≤103，1≤wi,vi≤103

## 2. Test cases

enter:

5 20

1 6

2 5

3 8

5 15

3 3

output:

120

## 3. Ideas

The complete knapsack problem does not require a clear division of items, so only a one-dimensional array is required d p dp dp is enough, dynamically updated in each calculation d p dp The value of the dp array.

- Status indicates: d p [ i ] : dp[i] : dp[i]: Indicates the maximum value that the backpack can hold when the backpack capacity is i.
- State transition equation: d p [ i ] = m a x ( d p [ i − w [ k ] + v [ k ] ) dp[i] = max(dp[i-w[k] + v[k]) dp[i]=max(dp[i−w[k]+v[k])(k represents the index of the traversed item, w[i] is the weight of the i-th item, v[i] is the k-th item the value of
- Boundary conditions: d p [ 0 ] = 0 dp[0] = 0 dp[0]=0, when the knapsack capacity is 0, the maximum value is also 0;

## 4. Algorithm implementation

public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); //Enter your code here... int n = scan.nextInt(), volume = scan.nextInt(); int[] w = new int[n]; int[] v = new int[n]; int[] dp = new int[volume+1]; for(int i = 0; i < n; i++){ w[i] = scan.nextInt(); v[i] = scan.nextInt(); } for(int i = 1; i <= volume; i++){ for(int j = 0; j < n; j++){ if(i >= w[j]){ dp[i] = Math.max(dp[i], dp[i-w[j]]+v[j]); } } } System.out.println(dp[volume]); scan.close(); } }