剑指offer10-1 斐波那契数列
def f(n):
a=0
b=1
for _ in range(n):
a,b=b,a+b
return a % 1000000007
大数求余
剑指offer10-11 青蛙跳台阶问题
def f(n):
a=1
b=2
for _ in range(1,n):
a,b=b,a+b
return a%1000000007
当a为1的时候 循环为(1,1) 不会走到循环里去 所以a=1
当a为2的时候循环为（1,2） a=b
也可以直接用菲波那切数列的解法 因为台阶为0的时候，f(0)=0
剑指offer42 连续子数组最大的和
状态转移方程 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圆圈中最后剩下的数
算法题:n个人，编号1-n，从第一个人开始数到k，第k个人出列，接着从k+1个人开始数k出列，依次类推，求最后剩下个那个人的编号
状态转移方程 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
没有太理解
还是递归好理解一点
def f(n):
if n==1:retun 0
x=f(n-1,m)
return (x+m)%n
假如只有一个数，则返回的index肯定为0
7、一楼到二楼有20个台阶，每一次能走1个或者2个，有多少种走法？
和斐波那契数列类似
若是台阶为1，只有1中走法，若是台阶为2，有2种走法，若要跳到n级只能从n-1和n-2台阶跳
递归实现：
def f(n):
if i==1:return 1
elif i==2:return 2
else:return f(n-1)+f(n-2)
动态规划实现：
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])
