Offer dynamic programming in Python and C++

Fibonacci sequence 2. Jump step 3. Abnormal jump step 4

The Fibonacci series

Topic describes

We all know the Fibonacci sequence, and now we want an integer n, so I want you to print the NTH term of the Fibonacci sequence (starting at 0, the 0th term is 0). n<=39

Train of thought

Fibonacci ratched series: F (1) = 1, F (2) = 1, F (n) = F (n – 1) + F (n – 2) (n > = 3, n ∈ n *)

Just define two integer variables, where b represents the following number and a represents the preceding number. Each time, the transformation is: A,b = b,a+b

python

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        # write code here
        if n<=0:
            return 0
        a = b = 1
        for i in range(2, n):
            a, b = b, a+b
        return b
Copy the code

C++

class Solution {
public:
    int Fibonacci(int n) {
        if(n<=0)
            return 0;
        int a =1;
        int b = 1;
        for(int i=2; i<n; i++) { int temp; temp = a +b; a = b; b = temp; }returnb; }};Copy the code

Dance steps

Topic describes

A frog can jump up one step or two at a time. Find out how many ways the frog can jump up a n step (different order counts different results).

Train of thought

In fact, it’s similar to Fibonacci, there’s one way for the frog to go up the first step, and two ways for the frog to go up the second step, the first way is to go up two steps, or two steps at a time, two ways. On the third step, the way from the first step, plus the way from the second step,

python

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number<=0:
            return 0
        if number==1:
            return 1
        a = 1
        b = 2
        for i in range(2, number):
            a , b = b, a+b
        return b
Copy the code

C++

class Solution {
public:
    int jumpFloor(int number) {
        if (number==0)return 0;
        if (number==1)return 1;
        if (number==2) return 2;
        int b=2;
        int a=1;
        int temp;
        for(int i=3; i<=number; i++) { temp = a + b; a = b; b = temp; }returntemp; }};Copy the code

Abnormal jump step

Topic describes

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.

Train of thought

N = 0, f (n) = 0. N = 1, f (n) = 1; N = 2, f (n) = 2; Let’s say we get to n steps, we can jump up at n minus 1 steps, or we can jump up at no n minus 1 steps, so f of n is equal to 2 times f of n minus 1.

The formula can also be deduced:

N = n: f(n) = F (n-1)+f(n-2)+… +f(n-(n-1)) + f(n-n) = f(0) + f(1) + f(2) + … + f(n-1)

Since f(n-1) = F (0)+ F (1)+f(2)+… + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + … + f(n-2)

So f(n) = f(n-1)+f(n-1)=2 times f(n-1)

python

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number<=0:
            return 0
        elif number ==1:
            return 1
        a = 1;
        for i in range(1, number):
            b = a*2
            a = b
        return b
            
Copy the code

C++

class Solution {
public:
    int jumpFloorII(int number) {
        if (number<=0)
            return 0;
        else if (number == 1)
            return 1;
        int a = 1;
        int b = 2;
        for(int i = 1; i<number; i++)
        {
            b = 2*a;
            a = b;
        }
        returnb; }};Copy the code

Matrix overlay

Topic describes

We can cover a larger rectangle with a smaller rectangle of 21 horizontal or vertical. How many ways are there to cover a 2* N rectangle with n small rectangles of 21 without overlapping?

Train of thought

The same idea as jumping up stairs, or seeing how well this person writes. www.nowcoder.com/questionTer…

python

# -*- coding:utf-8 -*-
class Solution:
    def rectCover(self, number):
        # write code here
        if number<=0:
            return 0
        if number==1:
            return 1
        a = 1
        b = 2
        for i in range(2, number):
            a , b = b, a+b
        return b
Copy the code

C++

class Solution {
public:
    int rectCover(int number) {
        if (number==0)return 0;
        if (number==1)return 1;
        if (number==2) return 2;
        int b=2;
        int a=1;
        int temp;
        for(int i=3; i<=number; i++) { temp = a + b; a = b; b = temp; }returntemp; }};Copy the code