本文共 2382 字，大约阅读时间需要 7 分钟。
# -*- coding:utf-8 -*-'''剪绳子题目描述给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。输入描述:输入一个数n，意义见题面。（2 <= n <= 60）输出描述:输出答案。示例1输入复制8输出复制18'''class Solution: def cutRope(self, number): # write code here if number < 2: return 0 if number == 2: return 1 if number == 3: return 2 #DP矩阵-max矩阵 max_ls = [0,1,2,3] #绳子大于3米，可以用动态规划的公式做，f(n)=f(i)*f(n-i) #13 22 31 #14 23 32 41 #5/2+1 #4/2+1 for i in range(4,number+1): max_1 = 0 for j in range(1,i/2+1): temp = max_ls[j]*max_ls[i-j] max_1 = max(max_1,temp) max_ls.append(max_1) return max_ls.pop()s = Solution()print(s.cutRope(8))
# -*- coding:utf-8 -*-'''机器人的运动范围地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？'''class Solution: def movingCount(self, threshold, rows, cols): # write code here markmatrix = [False] * (rows * cols) count = self.GetNum(threshold, rows, cols, 0, 0, markmatrix) return count #递归函数 def GetNum(self, threshold, rows, cols, row, col, markmatrix): count = 0 #是否符合规定 符合就递归 if self.GetSum(threshold, rows, cols, row, col, markmatrix): markmatrix[row * cols + col] = True count = 1 + self.GetNum(threshold, rows, cols, row - 1, col, markmatrix) + \ self.GetNum(threshold, rows, cols, row, col - 1, markmatrix) + \ self.GetNum(threshold, rows, cols, row + 1, col, markmatrix) + \ self.GetNum(threshold, rows, cols, row, col + 1, markmatrix) return count #判断条件 def GetSum(self, threshold, rows, cols, row, col, markmatrix): if row >= 0 and row < rows and col >= 0 and col < cols and self.getDigit(row) + self.getDigit( col) <= threshold and not markmatrix[row * cols + col]: return True return False #数位之和大于k def getDigit(self, number): sumNum = 0 while number > 0: sumNum += number % 10 number = number // 10 return sumNums = Solution()print(s.movingCount(40,40,18))
转载地址：http://lmgof.baihongyu.com/