怎么做网站后门,海南网站建设哪家好,公司网站建设管理,科技文化网站建设方案不能放弃治疗,每天都要进步#xff01;#xff01;
什么时候使用动态规划呢#xff1f;
1. 求一个问题的最优解
2. 大问题可以分解为子问题#xff0c;子问题还有重叠的更小的子问题
3. 整体问题最优解取决于子问题的最优解#xff08;状态转移方程#xff09;
4. 从上往…不能放弃治疗,每天都要进步
什么时候使用动态规划呢
1. 求一个问题的最优解
2. 大问题可以分解为子问题子问题还有重叠的更小的子问题
3. 整体问题最优解取决于子问题的最优解状态转移方程
4. 从上往下分析问题从下往上解决问题
5. 讨论底层的边界问题
实例1割绳子问题
题目给你一根长度为n的绳子请把绳子剪成m段 (m和n都是整数n1并且m1)每段绳子的长度记为k[0],k[1],…,k[m]. 请问k[0]k[1]…*k[m]可能的最大乘积是多少例如当绳子的长度为8时我们把它剪成长度分别为2,3,3的三段此时得到的最大乘积是18.
思路f(n)max{f(i)f(n-i)}想发与实现是2个方法想的时候是递归实现的时候是从底层至最上面。
实现1米最12米最大是2,3米最大是3,4米最大是4依次类推求n米的最大切割
算法复杂度On2#-*- coding: utf-8 -*
defmaxCutString(length):#这三行代表输入的绳子长度为1,2,3时发生切割动作最大的乘积
if length 2:return0if length 2:return 1
if length 3return 2
#绳子不断切割当切割到长度为1,2,3时不能继续切割直接返回1,2.3
arr[0,1,2,3]#记录绳子长度为i时候的最大乘积arr[i]
for i in range(4,length1):
maxs0for j in range(1,i/21):
multarr[j]*arr[i-j]if maxs
maxsmult
arr.append(maxs)returnarr[length]print maxCutString(8
View Code
实例2最大连续子项和
思路
实现maxtmp记录临时子项和遇到的每一个数不断累加当maxtmp为负时清空从下一个数开始从新累加当累加的数大于maxsum时将值赋给maxsum
复杂度O(n)#-*- coding: utf-8 -*#!usr/bin/python
defmaxSum(lists):
maxsum0
maxtmp0for i inrange(len(lists)):if maxtmp0:
maxtmplists[i]else:
maxtmplists[i]if maxtmp maxsum:
maxsummaxtmpreturnmaxsum
lists[1,3,-3,4,-6,5]print maxSum(lists)
View Code
还有一种暴力求解双层遍历复杂度O(n2)#-*- coding: utf-8 -*#!usr/bin/python
defmaxSum(lists):
maxsum0for i inrange(len(lists)):
maxtmp0for j inrange(i,len(lists)):
maxtmplists[j]if maxtmp maxsum:
maxsummaxtmpreturnmaxsum
lists[1,3,-3,4,-6,5]print maxSum(lists)
View Code
实例3放苹果
把M个同样的苹果放在N个同样的盘子里允许有的盘子空着不放问共有多少种不同的分法用K表示511和151 是同一种分法。
思路f(m,n) f(m,n-1)f(m-n,n)
设f(m,n) 为m个苹果n个盘子的放法数目则先对n作讨论
当nm必定有n-m个盘子永远空着去掉它们对摆放苹果方法数目不产生影响。即if(nm) f(m,n) f(m,m)
当nm不同的放法可以分成两类
1、有至少一个盘子空着即相当于f(m,n) f(m,n-1);
2、所有盘子都有苹果相当于可以从每个盘子中拿掉一个苹果不影响不同放法的数目即f(m,n) f(m-n,n).
而总的放苹果的放法数目等于两者的和即 f(m,n) f(m,n-1)f(m-n,n)
递归出口条件说明
1.当n1时所有苹果都必须放在一个盘子里所以返回
2.当没有苹果可放时定义为种放法
递归的两条路第一条n会逐渐减少终会到达出口n1;
第二条m会逐渐减少因为nm时我们会return f(m,m) 所以终会到达出口m0#!usr/bin/python
deff(m,n):if (m0 or n1):return 1
if m
linesmap(int,raw_input().strip().split())print f(lines[0],lines[1])
View Code
实例四青蛙跳台阶问题
1.如果青蛙可以一次跳 1 级也可以一次跳 2 级。问要跳上第 n级台阶有多少种跳法
思路:f(n)f(n-1)f(n-2) 第n级别只能由n-1级别和第n-2级别的青蛙跳到#-*- conding: utf-8 -*#递归解法
deff(n):if n1:return 1
elif n2:return 2
else:return f(n-1)f(n-2)print f(8)#自下到上解法
deff2(n):
arr[0,1,2]for i in range(3,n1):
tmparr[i-1]arr[i-2]
arr.append(tmp)returnarr[n]print f2(8)
View Code
2.如果青蛙可以一次跳 1 级也可以一次跳 2 级一次跳 3 级…一次跳 nn 级。问要跳上第 n级台阶有多少种跳法#.*. coding:utf-8 -*#递归解法
deff(n):if n1:return 1
else:return 2*f(n-1)print f(8)#自下而上解法
deff2(n):
arr[0,1,2]for i in range(3,n1):
tmp2*arr[i-1]
arr.append(tmp)returnarr[n]print f2(8)
View Code
