2. Dynamic rule 1

Fibonacci

recursive

Int Fibonacci(int n) {if(n == 0)return 0; if(n == 1 || n == 2)return 1; return Fibonacci(n-1)+Fibonacci(n-2); }Copy the code

The time complexity is O(2^n) and increases exponentially with the increase of n, which is inefficient and easy to cause stack overflow

Dynamic gauge

The problem

The value of the NTH term of the sequence

state

The ith term of the sequence

Transfer equation

F(i) = F(i-1)+F(i-2)

The initial state

F(0) = 0

F(1) = 1

return

F(n)

code

Moving gauge (recording intermediate results)

Int Fibonacci(int n) {// vector<int> F(n+1, 0); // initialize F(0) = 0,F(1) = 1; for(int i=2; i<=n; ++i){ F[i] = F[i-1] + F[i-2]; } return F[n]; }Copy the code

Time complexity O(n) space complexity O(n)

Moving gauge (do not record intermediate results)

Int Fibonacci(int n) {if(n<=1)return n; int cur=1, pre=0; for(int i=2; i<=n; ++i){ int tmp = cur; cur += pre; pre = tmp; } return cur; }Copy the code

Time complexity O(n) space complexity O(1)

A frog can jump up one step at a time, or two… It can also jump up n levels. Find out how many ways the frog can jump up n steps.

The problem

Number of ways to jump up n steps

state

N =4 n=4

F(1) = {1}

F (2) = {1, 1} {2}

F(3) = {1,2} {1,1,1} {2,1} {3}

F (4) = {1, 3},1,2 {1} {2} {1, 2, 1},1,1,1 {1} {2,1,1} {3, 1} {4}

F(1) = F(0) = 1

F(2) = F(1) + F(0) = 2

F(3) = F(2) + F(1) + F(0) = 4

F(4) = F(3) + F(2) + F(1) + F(0) = 8

Number of ways to jump up step I:

F(i) = F(i-1)+F(i-2)+… +F(0)

Transfer equation

So the transfer equation is zero

F(i) = F(i-1)+F(i-2)+… +F(0)

F(i-1) = F(i-2)+F(i-3)+… +F(0)

–>

F(i) = 2*F(i-1)

The initial state

F(1) = 1

return

F(n)

code

recursive

Int jumpFloorII(int number) {if(number == 1) return 1; return 2*jumpFloorII(number-1); }Copy the code

Moving gauge (recording intermediate results)

Int jumpFloorII(int number) {// vector<int> arr(number+1,0); // F(1) = 1 arr[1] = 1; //F(i) = 2*F(i-1) for(int i=2; i<=number; ++i) arr[i] = 2*arr[i-1]; return arr[number]; }Copy the code

Time complexity O(n), space complexity O(n)

Moving gauge (do not record intermediate results)

Int jumpFloorII(int number) {// iterate if(number == 1) return 1; int cur = 1; for(int i=2; i<=number; ++i) cur *= 2; return cur; }Copy the code

Time complexity O(n), space complexity O(1)

So, it’s easier to use a shift

int jumpFloorII(int number) {
    return 1 << (number-1);
}
Copy the code

Time complexity O(1) : shift operation is used

If the frog jumps to the NTH step, it is known that it must have jumped to the NTH step. For the n-1 step before the NTH step, there are two situations: either he jumped to the NTH step or he did not jump to the NTH step

2^{n-1}
Copy the code

Jump method

A frog can jump up one step or two at a time. Find out how many ways the frog can jump up n steps.

The problem

Number of ways to jump up n steps

state

F(1) = F(0) = 1

F(2) = F(1) + F(0) = 2

F(3) = F(2) + F(1) = 3

Number of ways to jump up i-steps: One step from I-1 and two steps from I-2

F(i) = F(i-1) + F(i-2)

Transfer equation

F(i) = F(i-1) + F(i-2)

The initial state

F(1) = F(0) = 1

return

F(n)

code

recursive

int jumpFloor(int number) {
    if(number == 0 || number == 1)return 1;
    return jumpFloor(number-1)+jumpFloor(number-2);
}
Copy the code

Moving gauge (recording intermediate results)

int jumpFloor(int number) { vector<int> arr(number+1, 0); // F(0) = F(1) = 1 arr[0] = arr[1] = 1; for(int i=2; i<=number; ++i) arr[i] = arr[i-1]+arr[i-2]; return arr[number]; }Copy the code

Time complexity O(n), space complexity O(n)

Moving gauge (do not record intermediate results)

int jumpFloor(int number) {
    if(number == 0 || number == 1)return 1;
    int cur = 1,pre = 1;
    for(int i=2; i<=number; ++i){
        int tmp = cur;
        cur += pre;
        pre = tmp;
    }
    return cur;
}
Copy the code

Time complexity O(n), space complexity O(1)

We can cover a larger rectangle with a 2 by 1 rectangle horizontally or vertically. How many ways are there to cover a large 2* N rectangle with n small 2*1 rectangles without overlapping?

The problem

How many ways can I cover a 2 by n rectangle

state

F(1) = 1 = F(0)

F(2) = 2 = F(1) + F(0)

F(3) = 3 = F(2) + F(1)

F(4) = 5 = F(3) + F(2)

Number of ways to fill a large rectangle with 2* I:

F(i) = F(i-1) + F(i-2)

Transfer equation

F(i) = F(i-1) + F(i-2)

The initial state

F(1) = F(0) = 1

return

F(n)

code

Both are Fibonacci sequences, so reference the classic frog jump step code is the same

Note that n=0 returns 0

Int rectCover(int number) {if(number<=2) return number; return rectCover(number-1)+rectCover(number-2); If (number < 2) return number; vector<int> arr(number+1, 0); // F(0) = F(1) = 1 arr[0] = arr[1] = 1; for(int i=2; i<=number; ++i) arr[i] = arr[i-1]+arr[i-2]; return arr[number]; If (number < 2) return number; int cur = 1,pre = 1; for(int i=2; i<=number; ++i){ int tmp = cur; cur += pre; pre = tmp; } return cur; }Copy the code

HZ occasionally tries to fool non-computer majors with professional questions. Today, after the test group meeting, he spoke again: in the old one-dimensional pattern recognition, it is often necessary to calculate the maximum sum of continuous subvectors, when the vectors are all positive, the problem is easily solved. But if the vector contains negative numbers, should it include some negative number and expect the positive number next to it to make up for it? For example: {6-3-2, 7, 15,1,2,2}, the largest and continuous vector son is 8 (starting from 0, until the third). Given an array, return the sum of its largest contiguous subsequence, would you be fooled by it? (The length of the subvector is at least 1)

For optimal problems, you can use a moving gauge

The problem

The maximum continuous sum of an array

Subproblem: array of local elements, maximum subsequence sum

state

The sum of the largest subsequence up to the ith element does not necessarily contain the ith element;

So the state is the largest contiguous subsequence ending in the ith element

Transfer equation

F(i) = max(F(i-1)+a[i], a[i])

The initial state

A subarray knows to be an element, so F[0] = a[0]

F[0] = a[0]

return

max(F[i])

code

Save the intermediate result to find the maximum of all local solutions

class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { if(array.empty()) return 0; //F[0] = a[0] vector<int> maxSum(array); for(int i=1; i<array.size(); ++i){ //F[i] = max(F[i-1]+a[i], a[i]) maxSum[i] = max(maxSum[i-1]+array[i], array[i]); } //max(F[i]) int ret = maxSum[0]; for(int i=1; i<maxSum.size(); ++i){ ret = max(ret, maxSum[i]); } return ret; }};Copy the code

Save the intermediate result control to a single layer loop

class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { if(array.empty()) return 0; //F[0] = a[0] vector<int> maxSum(array); int ret = maxSum[0]; for(int i=1; i<array.size(); ++i){ //F[i] = max(F[i-1]+a[i], a[i]) maxSum[i] = max(maxSum[i-1]+array[i], array[i]); //max(F[i]) ret = max(ret, maxSum[i]); } return ret; }};Copy the code

The intermediate results are not saved

class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { if(array.empty()) return 0; //F[0] = a[0] int ret = array[0]; for(int i=1; i<array.size(); ++i){ //F[i] = max(F[i-1]+a[i], a[i]) array[i] = max(array[i-1]+array[i], array[i]); //max(F[i]) ret = max(ret, array[i]); } return ret; }};Copy the code

Given a string s and a set of dict words, determine whether S can be split into a sequence of words with Spaces such that all words in the sequence are dict words (the sequence can contain one or more words). For example, given s=”nowcode”; Dict =[“now”, “code”]. Returns true because “nowcode” can be split into “nowcode”.

The problem

Whether words can be successfully divided

Subquestion: Whether the first few characters of a word can be successfully split

State ^[a description of a recursion in which states are defined so that previous states can be used in this and subsequent states]

Take s=”leetcode”, dict = [“leet”, “code”] as an example

F[0] = “l” –> false

F[1] = “le” –> false

F[2] = “lee” –> false

F[3] = “leet” –> true

F[4] = F[4]+”c” –> false

F[5] = F[3]+”co” –> false

F[6] = F[3]+”cod” –> false

F[7] = F[3]+”code” –> true

Get the state:

The first I characters of a word can be successfully split

Transfer equation

F[I]: j < I &&f [j] &&substr [j+1, I] whether it can be found in the dictionary

The initial state

F[0] = substr[0,0] can be found in the dictionary

return

F[s.size()-1]

code

Moving rules of c + +

class Solution { public: bool wordBreak(string s, unordered_set<string> &dict) { bool* F = new bool[s.size()](); for (int i = 0; i < s.size(); + + I) {/ / F [0] = substr [0, 0] / / judge the whole [0, I] is not in the dictionary [I] = F (dict. Find (s.s ubstr (0, I + 1)). = dict.end()); for (int j = 0; j < i; + + j) {/ / F [j] && substr [I] j + 1, whether can be found in the dictionary if (F [j] && dict. Find (s.s ubstr (j + 1, I, j))! = dict.end()) { F[i] = true; break; } } } return F[s.size() - 1]; }};Copy the code

Dynamic gauge Java

import java.util.Set; public class Solution { public boolean wordBreak(String s, Set<String> dict) { boolean[] F = new boolean[s.length()]; for(int i=0; i<s.length(); ++ I){// Determine if STR on [0, I] is in dict F[I] = dict.contains(s.substring(0, I +1)); for(int j=0; j<i; + + j) {/ / F [j] && [I] j + 1, whether can be found in the dictionary if (F [j] && dict. The contains (s.s ubstring (j + 1, I + 1))) {F [I] = true; break; } } } return F[s.length()-1]; }}Copy the code