动态规划

袋鼠从起点开始跳,问到终点有多少种不同的跳跃方式

题目 有一只袋鼠,它跳跃一次的方式只有两种:①一次跳1米 ②一次跳3米,现在有一段10米长的路,袋鼠从起点开始跳,问到终点有多少种不同的跳跃方式? 方法1:生成二叉树生成 每一步有两种选择:1米或者3米,所以解集是一棵二叉树,每一个节点代表一种选择。 假设当前运动位置是S,则S = sum(根节点 + ... +当前节点)。(我不知道markdown如何打数学公式,google出来的都没成功,凑合着看吧) 当前运动位置 > 10m,说明路走完了。结束当前路径搜索。 遍历二叉树,找到所有sum <?php const TOTAL_STEP = 10; const OPTION_STEP1 = 1; const OPTION_STEP3 = 3; $table = []; $count = 0; // 生成遍历二叉树 function gene1($path, $dist){ global $table; global $count; $path1 = 0; $path2 = 0; $count += 1; if($dist < TOTAL_STEP){ $path1 = $path . OPTION_STEP1; $set1 = gene1($path1, $dist +...

41. 最大子数组

动态规划大法。 第一步,建模,得出递推公式 有一个数组A[n], 对于A[i] (0<i<n)位置向前(0位置方向)最大和为C[i], 那么 C[i] = Max(C[i-1] + A[i], A[i]) 终止条件 C[0] = A[0] 这样子我们就得到了对于任意一个位置 0 <= i < n,数组中从0到i的最大子串和。 但是我们的目标并不是求i位置,最大子串和。我们的目标是求整个数组上,最大子串和,也就是 Opt(A) = Max(C[i]), 0 <= i < n 第二步,试着实现算法 class Solution: def maxSubArray(self, nums): # write your code here length = len(nums) c = [0] * length c[0] = nums[0] maxSum = c[0] i = 1 while i < length: if c[i-1] + nums[i] > nums[i]: c[i] = c[i-1] + nums[i] el...
执行时间: 33.348083496094 毫秒