劍指offer10-1 斐波那契數(shù)列
def f(n):
a=0
b=1
for _ in range(n):
a,b=b,a+b
return a % 1000000007
大數(shù)求余
劍指offer10-11 青蛙跳臺(tái)階問題
def f(n):
a=1
b=2
for _ in range(1,n):
a,b=b,a+b
return a%1000000007
當(dāng)a為1的時(shí)候 循環(huán)為(1,1) 不會(huì)走到循環(huán)里去 所以a=1
當(dāng)a為2的時(shí)候循環(huán)為（1,2） a=b
也可以直接用菲波那切數(shù)列的解法 因?yàn)榕_(tái)階為0的時(shí)候丑罪，f(0)=0
劍指offer42 連續(xù)子數(shù)組最大的和
狀態(tài)轉(zhuǎn)移方程 dp[i] = max(dp[i-1]+nums[i],nums[i])
def f(nums):
dp=[None]*len(nums)
dp[0]=nums[0]
for i in range(len(nums)):
dp[i]=max(dp[i-1]+nums[i],.nums[i])
return max(dp)
劍指offer62圓圈中最后剩下的數(shù)
算法題:n個(gè)人凤壁，編號(hào)1-n，從第一個(gè)人開始數(shù)到k客扎，第k個(gè)人出列，接著從k+1個(gè)人開始數(shù)k出列徙鱼，依次類推，求最后剩下個(gè)那個(gè)人的編號(hào)
狀態(tài)轉(zhuǎn)移方程 dp[i]=(dp[i-1]+m)%i
def f(n):
x=0
for i in range(2,n+1):
x=(x+m)%i
return x
沒有太理解
還是遞歸好理解一點(diǎn)
def f(n):
if n==1:retun 0
x=f(n-1,m)
return (x+m)%n
假如只有一個(gè)數(shù)厌衙，則返回的index肯定為0
7、一樓到二樓有20個(gè)臺(tái)階婶希，每一次能走1個(gè)或者2個(gè)，有多少種走法喻杈？?
和斐波那契數(shù)列類似
若是臺(tái)階為1，只有1中走法筒饰，若是臺(tái)階為2，有2種走法瓷们，若要跳到n級(jí)只能從n-1和n-2臺(tái)階跳
遞歸實(shí)現(xiàn)：
def f(n):
if i==1:return 1
elif i==2:return 2
else:return f(n-1)+f(n-2)
動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)：
nums=[]
nums[0]=0
nums[1]=1
nums[2]=2
for i in range(3,int(n)+1):
nums[i]=nums[i-1]+nums[i-2]
print(nums[n])
