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();
    }
}