第一题 跳跃游戏
题目
贪婪解法
对于每个下标而言，元素规定了它能够达到的最大间隔
因而这部分间隔范畴内的下标都是能够到达的
.
例如示例1：nums = [2,3,1,1,4]
.
对于下标0而言，它能够抉择下标1或者下标2
抉择下标1.能够达到下标4
抉择下标2，能够达到下标3
.
因为本题返回值为布尔类型，无需存储跳跃门路
咱们只需记住跳跃能达到的最远下标即可，
对于最远下标以内，咱们总能找到一条能够到达的门路
因而咱们能够失去公式
maxIndex=max(maxIndex,i+nums[i])
直到最远下标到达最初一个下标
if maxIndex>=n-1 {return true}
核心思想为 贪婪算法 ，即优先思考可取得的最佳的解法
对于每个下标，咱们都将其最优解退出思考范畴
具体代码
func canJump(nums []int) bool { n:=len(nums) var maxIndex int for i:=0;i<n;i++{ if i>maxIndex{return false} maxIndex=max(maxIndex,i+nums[i]) if maxIndex>=n-1 {return true} } return false}func max(x int,y int)int { if x<y{ return y }else { return x }}官解
动静布局解法
在用动静布局求解之前，让咱们在强调一下动静布局的几个步骤
具体学习能够参考
https://labuladong.gitee.io/a...
https://houbb.github.io/2020/...
而对于本题而言
代码
func canJump(nums []int) bool { n:=len(nums) a:=nums[0] // a=dp[i-1] for i:=1;i<n;i++ { if a==0 {return false} a=max(a-1,nums[i]) // a=dp[i] } return true}func max(x int,y int)int { if x<y{ return y }else { return x }}复杂度剖析
工夫复杂度：O(n)，其中 n 为数组的大小。只须要拜访 nums 数组一遍，共 n 个地位。
空间复杂度：O(1) ，常数级的空间开销。
第二题 不同门路
题目
思路
dp
这是组合数学中经典的格路模型，它的计算与杨辉三角是等价的
都是
f(i,j)=f(i−1,j)+f(i,j−1)
代码
func uniquePaths(m int, n int) int { //初始化 arr := make([][]int, m) for i := range arr { arr[i] = make([]int, n) arr[i][0]=1 } for i:=range arr[0]{ arr[0][i]=1 } if m==1||n==1 {return 1} for i:=1;i<m;i++{ for j:=1;j<n;j++{ arr[i][j]=arr[i-1][j]+arr[i][j-1] } } return arr[m-1][n-1]}复杂度剖析
工夫复杂度：O（mn），计算了m*n矩阵个数值，最终失去第m行第n列的答案
空间复杂度：O（mn），借助二维数组失去最终答案
同时
组合数学
go语言中提供了计算排列组合数的办法
因而咱们也能够间接调用该办法获取答案
办法具体参数为
第m，n项的组合数为
故代码为
func uniquePaths(m, n int) int { return int(new(big.Int).Binomial(int64(m+n-2), int64(n-1)).Int64())}