劍指offer 動(dòng)態(tài)規(guī)劃 Python and C++
1屡江、斐波拉契數(shù)列
2单旁、跳臺(tái)階
3腰涧、變態(tài)跳臺(tái)階
4、矩陣覆蓋
斐波拉契數(shù)列
題目描述
大家都知道斐波那契數(shù)列犯祠，現(xiàn)在要求輸入一個(gè)整數(shù)n旭等，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)（從0開始，第0項(xiàng)為0）衡载。
n<=39
思路
斐波拉契數(shù)列：F(1)=1搔耕，F(xiàn)(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
只需定義兩個(gè)整型變量，b表示后面的一個(gè)數(shù)字弃榨，a表示前面的數(shù)字即可菩收。每次進(jìn)行的變換是： 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
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;
}
return b;
}
};
跳臺(tái)階
題目描述
一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)鲸睛。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法（先后次序不同算不同的結(jié)果）娜饵。
思路
其實(shí)和斐波拉契差不多，青蛙上第一個(gè)臺(tái)階的時(shí)候官辈，是一種方法箱舞，第二個(gè)臺(tái)階的時(shí)候是兩種分法，第一種就是拳亿，走兩個(gè)一階梯晴股，或者一次走兩個(gè)階梯，兩種方法肺魁。第三個(gè)臺(tái)階的時(shí)候电湘，是從第一個(gè)臺(tái)階的方法，加上從第二個(gè)臺(tái)階來的鹅经，
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
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;
}
return temp;
}
};
變態(tài)跳臺(tái)階
題目描述
一只青蛙一次可以跳上1級(jí)臺(tái)階寂呛，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法瘾晃。
思路
n=0時(shí),f(n)=0昧谊；n=1時(shí),f(n)=1；n=2時(shí),f(n)=2酗捌；假設(shè)到了n級(jí)臺(tái)階呢诬，我們可以n-1級(jí)一步跳上來，也可以不經(jīng)過n-1級(jí)跳上來胖缤，所以f(n)=2*f(n-1)尚镰。
推公式也能得出：
n = n時(shí)：f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) = f(0) + f(1) + f(2) + ... + f(n-1)
由于f(n-1) = f(0)+f(1)+f(2)+ ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
所以f(n) = f(n-1)+f(n-1)=2*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
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;
}
return b;
}
};
矩陣覆蓋
題目描述
我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問用n個(gè)21的小矩形無重疊地覆蓋一個(gè)2*n的大矩形哪廓，總共有多少種方法狗唉？
思路
和跳臺(tái)階的一樣的思路，或者看這個(gè)人寫的挺好的涡真。
https://www.nowcoder.com/questionTerminal/72a5a919508a4251859fb2cfb987a0e6?answerType=1&f=discussion
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
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;
}
return temp;
}
};
