# 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[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

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 dp=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);
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();
}
} Posted by Boxerman on Thu, 08 Dec 2022 16:07:08 +0530