This article is participating in the “Java Theme Month – Java brush questions clock”, see < activity links > for more details.

【Java brush questions punch card 】 Brushing questions is much better than playing games, and the sense of achievement is getting stronger and stronger. I insist on brushing several questions every day, exercising for 30 minutes every day, waiting for 8-block abs and waiting for offers from big factories.

Then do it! This column is all about dynamic planning, I will start from the shallow to the deep, step by step, brush questions is such a need for continuous memory – Ebbinghaus memory method 2121112. There isn’t much about dynamic programming, but it’s a must for every programmer


This is a classic 😄😄😄 \color{green}{😄 😄 😄 ~}

What problem can I choose to do dynamic programming?

Counting 1.

  • How many ways can I get to the bottom right corner
  • How many ways can I pick the sum of k numbers yes is sum

2. Find the maximum and minimum

  • The maximum numeric sum of the path from the upper left corner to the lower right corner
  • Maximum ascending subsequence length

3. Seek existence

  • Stone game, whether the first hand will win
  • Can we pick k numbers such that the sum is sum

Leecode 115. Different subsequences

Given a string s and a string t, count the number of occurrences of t in a subsequence of S.

A subsequence of strings is a new string formed by deleting some (or none) characters without interfering with the relative positions of the remaining characters.

(For example, “ACE” is a subsequence of “ABCDE”, but “AEC” is not)

The question data ensures that the answers fit into the range of 32-bit signed integers.

Example 1:

Enter: s = “rabbbit”, t = “rabbit”

Output: 3

Explanation: As shown below, there are three ways to get “rabbit” from S.

(Top arrow symbol ^ indicates the selected letter)

rabbbit

^ ^ ^ ^ ^ ^

rabbbit

^ ^ ^ ^ ^ ^

rabbbit