关于golang:golangleetcode中级跳跃游戏不同路径

第一题 跳跃游戏

题目

贪婪解法

对于每个下标而言，元素规定了它能够达到的最大间隔

因而这部分间隔范畴内的下标都是能够到达的
.

例如示例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())
}