本想撸完迷宫去上个厕所，却憋了2个小时，解法倒是很简单，但是为啥特么总有傻X把入口堵死。那还走个🔨。不同路径一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）

等差数列划分如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。子数组 是数组中的一个连续序列。最佳观光组合给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。返回一对观光景点能取得的最高分。等差数列划分解题思路定义等差数列 一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列 取数组第一，二个元素先求出公差，从数组下标2开始迭代，判断当前元素和前一个元素的差是否等于公差，若等于则计数，如果不是重新计算公差，然后计数器清零。每次计算总数代码实现func numberOfArithmeticSlices(nums []int) int { if len(nums)<3{ return 0 } tolerance:=nums[1]-nums[0] total,count:=0,0 for i:=2;i<len(nums);i++{ if nums[i]-nums[i-1]==tolerance{ total++ }else{ tolerance=nums[i]-nums[i-1] total=0; } count+=total } return count}最佳观光组合解题思路定义等差数列 观光组合的得分为 values[i] + values[j] + i - j 代码实现func maxScoreSightseeingPair(values []int) int { a,b,max:=0,1,0 for b<len(values) { pre:=values[a]+a-b max = MathMax(max,pre+values[b]) if values[b]>pre{ a=b } b++ } return max}func MathMax(a,b int)int{ if a>b{ return a } return b}

下降路径问题931. 下降路径最小和给你一个n x n的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]输出：13解释：下面是两条和最小的下降路径，用加粗+斜体标注：[[2,1,3], [[2,1,3], [6,5,4], [6,5,4], [7,8,9]] [7,8,9]]解決这类问题我们可以自上而下的来解决问题：找当前层的最小值，那么就要把当前层的最小值的上方来按照对应的规则来递推前一层的最小值,如此类推 循环到最后一层,func minFallingPathSum(matrix [][]int) int { ans:=math.MaxInt32 for i:=1;i<len(matrix);i++{ for j:=0;j<len(matrix);j++{ if j==0{ matrix[i][j]+=min(matrix[i-1][0],matrix[i-1][j+1]) }else if j==len(matrix)-1{ matrix[i][j]+=min(matrix[i-1][j-1],matrix[i-1][j]) }else{ matrix[i][j]+=min(matrix[i-1][j+1],min(matrix[i-1][j-1],matrix[i-1][j])) } } } for i:=0;i<len(matrix);i++{ ans=min(ans,matrix[len(matrix)-1][i]) } return ans}func min(a,b int)int{ if a>b{ return b } return a}120. 三角形最小路径和给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标+ 1 的两个结点。也就是说，如果正位于当前行的下标 i，那么下一步可以移动到下一行的下标 i 或 i + 1 。输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]输出：11解释：如下面简图所示： 2 3 4 6 5 74 1 8 3自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。三角形下降也是同样的道理，只不过规则的选取变成了当前行 ↓ ↘ 那么我们从当前层往上找，难道就是取得 ↑ ↖func minimumTotal(triangle [][]int) int { if len(triangle)==0{ return 0 } if len(triangle)==1{ return triangle[0][0] } ans:=math.MaxInt32 for i:=1;i<len(triangle);i++{ for j:=0;j<=i;j++{ if j==0 { triangle[i][j]+=triangle[i-1][j] }else if j==i{ triangle[i][j]+=triangle[i-1][j-1] }else{ triangle[i][j]+=min(triangle[i-1][j-1],triangle[i-1][j]) } } } for i:=0;i<len(triangle);i++{ ans=min(ans,triangle[len(triangle)-1][i]) } return ans}func min(a,b int)int{ if a>b{ return b } return a }

股票买卖

典型的动态规划问题,从入门阶动态规划到引入其他数据结构的演变之路

数据结构和算法-动态规划（爬楼梯）

title: 数据结构和算法之动态规划author: Moodtags:数据结构和算法categories:动态规划date: 2020-03-08 13:48:00动态规划在数学上的递归表示的问题在计算机上都可以转化为递归的算法，在大多数情况下来看，能够对朴素的穷举提升效率，但是在实际情况来看呢，