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