本文共 5823 字，大约阅读时间需要 19 分钟。

剑指offer || 动态规划

剑指offer中有关动态规划的题目汇总

面试题14：剪绳子

题目：剪绳子

​ 给你一根长度为n的绳子，请把绳子剪成m段（m,n都是整数，n > 1 并且 m > 1), 每段绳子的长度记为k[0],k[1],…,k[m]。请问 k[0] * k[1]* …*k[m]可能的最大乘积是多少？

例子：当绳子的长度是8时，我们把它剪成长度为2、3 、3的三段，此时的最大乘积是18 `

思路

• 动态规划

代码

#################面试题14########################剪绳子class Solution:    def maxProdectAfterCutting_solution(self,length):        product = []        if length <2:            return 0        elif length == 2:            return 1        elif length == 3:            return 2        product.extend([0,1,2,3])        max = 0        for i in range(4,length+1):            for j in range(1,i//2+1):                area = product[j] * product[i-j]                if max < area:                    max = area            product.append(max)        return max

测试

################测试1##################功能测试s = Solution()s.maxProdectAfterCutting_solution(5)

面试题42：连续子数组的最大和

题目：连续子数组的最大和

​ 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)

输入： 数组[1,-2,3,10,-4,7,2,-5],和最大的子数组为[3,10,-4,7,2]

输出：，因此输出该数组的和为18

思路

代码

#################面试题42########################连续子数组的最大和def FindGreatestSumOfSubArray(Array):    if not Array:        return     n = len(Array)    maxSumArrayOfsubArray = [0] *(n+1)    maxSum = float('-inf')    for i in range(1,n+1):        if maxSumArrayOfsubArray[i-1] <= 0:            maxSumArrayOfsubArray[i] = Array[i-1]        else:            maxSumArrayOfsubArray[i] = maxSumArrayOfsubArray[i-1] + Array[i-1]        if maxSum < maxSumArrayOfsubArray[i]:            maxSum = maxSumArrayOfsubArray[i]    return maxSum

测试

################测试1##################功能测试#Array = [1,-2,3,10,-4,7,2,-5]result = FindGreatestSumOfSubArray(Array)print(result)Array = [-2,-3,-10,-4,-7,-2,-5]result = FindGreatestSumOfSubArray(Array)print(result)Array = [2,3,10,4,7,2,5]result = FindGreatestSumOfSubArray(Array)print(result)

面试题47：礼物的最大价值

题目：礼物的最大价值

​ 在一个m*n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值，可以从棋盘的左上角开始拿格子里的礼物，并每次向左或右移动一格，直到到达棋盘的右下角。给定棋盘及其礼物，计算最多能拿到多少价值的礼物

例如：

1 10 3 8

12 2 9 6

5 7 4 11

3 7 16 5`

思路

• 动态规划求解
• $f(i,j) = max(f(i-1,j) , f(i,j-1)) + gift[i,j]$

代码

#################面试题47########################礼物的最大价值def getMaxValue_solution1(values):    if not values:        return 0    rows = len(values)    if not isinstance(values[0], list):        maxValue = sum(values)        return maxValue    else:        cols = len(values[0])    if cols == 1:        maxValue = 0        for row in range(rows):            maxValue += values[row][0]        return maxValue    maxValues = [[0] * cols] * rows    for i in range(rows):        for j in range(cols):            left = 0            up = 0            if i > 0:  # i=0 边界                up = maxValues[i - 1][j]            if j > 0:                left = maxValues[i][j - 1]            maxValues[i][j] = max(left, up) + values[i][j]    maxValue = maxValues[rows - 1][cols - 1]    return maxValue  #########优化############## 只用一个一维数组来代替二维数组maxValues# 该数组前面j个数字分别是当前i行前面j个格子礼物的最大价值# 之后的数字分别保存i-1行，n-j个格子的礼物的最大价值def getMaxValue_solution2(values):    if not values:        return 0    rows = len(values)    if not isinstance(values[0], list):        maxValue = sum(values)        return maxValue    else:        cols = len(values[0])    if cols == 1:        maxValue = 0        for row in range(rows):            maxValue += values[row][0]        return maxValue    maxValues = [0] * cols    for i in range(rows):        for j in range(cols):            left = 0            up = 0            if i > 0:  # i=0 边界                up = maxValues[j]            if j > 0:                left = maxValues[j - 1]            maxValues[j] = max(left, up) + values[i][j]    maxValue = maxValues[cols - 1]    return maxValue

测试

################测试1##################功能测试# 功能测试# 多行多列的矩阵values = [[1, 10, 3, 8], [12, 2, 9, 6], [5, 7, 4, 11], [3, 7, 16, 5]]getMaxValue_solution1(values)# 一行或一列矩阵values = [1, 10, 3, 8]  # 一行getMaxValue_solution1(values)values = [[1], [10], [3], [8]]  # 一列getMaxValue_solution1(values)# 只有一个数字的矩阵values = [1]getMaxValue_solution1(values)# 特殊输入测试getMaxValue_solution1(None)##############优化后测试########### 功能测试# 多行多列的矩阵values = [[1, 10, 3, 8], [12, 2, 9, 6], [5, 7, 4, 11], [3, 7, 16, 5]]getMaxValue_solution2(values)# 一行或一列矩阵values = [1, 10, 3, 8]  # 一行getMaxValue_solution2(values)values = [[1], [10], [3], [8]]  # 一列getMaxValue_solution2(values)# 只有一个数字的矩阵values = [1]getMaxValue_solution2(values)# 特殊输入测试getMaxValue_solution2(None)

面试题48：最长不含重复字符的子字符串

题目：最长不含重复字符的子字符串

​ 请从字符串中找出一个最长的不包含重复字符的子字符串，计算最长该子字符串的长度.假设字符串中只包含’a’ ~ ‘z’ 的字符

`输入： 字符串’arabcacfr’

输出：最长的不包含重复字符的子字符串是'acfr'

思路

动态规划

$f(i)$ :以第i个字符为结尾的不包含重复字符的子字符串的最长长度

(1) 第i个字符之前没出现过，$f(i) = f(i-1) +1$

(2) 第i个字符之前已经出现过。

​ 计算第i个字符和它上次出现在字符串中的位置的距离，d

​ 1、$d <= f(i-1)$ 第i个字符上次出现在f(i-1)对应的最长子字符串之中

​ $f(i) = d$

​ 2、$d > f(i-1)$第i个字符上次出现在f(i-1)对应的最长子字符串之前

​ $f(i) = f(i-1) + 1$

代码

#################面试题48########################最长不含重复字符的子字符串def longestSubstringWithoutDuplication(string):    curLength = 0    maxLength = 0    position = [-1] * 26  # 26个字母    if not string:        return None    for i in range(len(string)):        preIndex = position[ord(string[i]) - ord('a')]        if preIndex < 0 or i - preIndex > curLength:            curLength += 1        else:            if curLength > maxLength:                maxLength = curLength            curLength = i - preIndex        position[ord(string[i]) - ord('a')] = i    if curLength > maxLength:        maxLength = curLength    return maxLength

测试

################测试1################## 功能测试# 包含多个字符的字符串longestSubstringWithoutDuplication('arabcacfr')# 只有一个字符的字符串longestSubstringWithoutDuplication('a')# 所有字符都相同的字符串longestSubstringWithoutDuplication('aaaa')# 特殊输入测试longestSubstringWithoutDuplication(None)

转载地址：http://scusn.baihongyu.com/