本文共 1985 字，大约阅读时间需要 6 分钟。
动态规划问题是面试题中的热门话题，如果要求一个问题的最优解（通常是最大值或者最小值），而且该问题能够分解成若干个子问题，并且小问题之间也存在重叠的子问题，则考虑采用动态规划。
使用动态规划特征：
1. 求一个问题的最优解 2. 大问题可以分解为子问题，子问题还有重叠的更小的子问题 3. 整体问题最优解取决于子问题的最优解（状态转移方程） 4. 从上往下分析问题，从下往上解决问题 5. 讨论底层的边界问题实例1
剪绳子问题 给你一根长度为N的绳子，请把绳子剪成M段（m,n都是整数），每段绳子的 长度记为k[0],k[1],k[2]…. 请问如何剪绳子使得k[0],k[1],k[2] 的乘积最大 例如 绳子长度8 最大乘积18 = 2*3*3def jianshengzi(n): # 先对边界问题进行求解，因为明显剪的值小于不剪的值 # 则提出先讨论这三种情况 if n < 2: return 0 if n == 2: return 1 #长度为2，只能剪成1*1 if n == 3: return 2 #长度为3，剪成2*1 > 1*1*1 #若绳子长于４呢,申请一个长度为50的数组 #罗列出切割的边界问题 h = [0]*50 h[0] = 0 h[1] = 1 h[2] = 2 h[3] = 3 # 递归问题是 f(n) = max{f(i)*f(n-i)} for i in range(4,n+1): maxs = 0 for j in range(1,i/2+1): mult = h[j] * h[i-j] if maxs < mult: maxs = mult h[i] = maxs # 每次J的迭代轮询出该长度的最大值 print h return h[n]print jianshengzi(8) 实例2
硬币问题 我们有面值为1元3元5元的硬币若干枚，如何用最少的硬币凑够11元？ 分析： 1 求问题的最优解：最小的硬币数 2 是否有子问题：f(n)表示的最少硬币数是是上一次拿时候的硬币数最少。 注意：f(n)是n元的最小硬币数，最后一次可拿的硬币数为1,3,5 则下一步 的最小硬币数为 f(n-vi) 它的状态变更不是按元数的，是按照上次拿的硬币钱目 3 状态转移方程为 f(n)= min(f(n-vi)+1) 4 边界问题(找到最后一个重复的问题) 这里 f(1)=1 ,f(2)=f(1)+f(1)=2 f(3)=min(1,f(2)+1) f(4)=f(3)+1 f(5)=1 5 从上往下分析问题，从下往上解决问题。def f(n): if n == 1: #把所有的边界问题找到 return 1 if n == 2: return 2 if n == 3: return 1 if n == 4: return 2 if n == 5: return 1 h = [1,3,5] minx = n for i in range(3): coun = f(n-h[i])+1 # 采用了递归的思想 这里是从上到下， if minx > coun: # 复杂度比较高 minx = coun return minxprint f(11)
def f(n): if n == 1: return 1 if n == 2: return 2 if n == 3: return 1 if n == 4: return 2 if n == 5: return 1 h = [1,3,5] for x in range(6,n+1): #从下往上的思维解决 minx = n for i in range(3): coun = f(x-h[i])+1 #从下往上的思维解决 if minx > coun: minx = coun return minxprint f(11)
转载地址：http://moiqi.baihongyu.com/