[golang] leetcode intermediate - jumping game & different paths

The first question is Jumping game

subject

Greedy solution

For each subscript , The element specifies the maximum distance it can reach

Therefore, the subscripts within this distance range are reachable
.

For example 1：nums = [2,3,1,1,4]
.

For subscripts 0 for , It can select Subscripts 1 Or subscript 2

Select subscript 1. You can reach the subscript 4

Select subscript 2, You can reach the subscript 3

.

Since the return value of this question is of boolean type , There is no need to store jump paths

We just need to remember the farthest subscript that a jump can reach ,

For the farthest subscript within , We can always find a way to get there

So we can get the formula

maxIndex=max(maxIndex,i+nums[i])

Until the farthest subscript reaches the last subscript

if maxIndex>=n-1 {return true}

The core idea is Greedy Algorithm , That is, give priority to the best solution that can be obtained

For each subscript , We all consider the optimal solution

Specific code

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
    }
}

Official interpretation

Dynamic programming solution

Before using dynamic programming , Let's emphasize the steps of dynamic programming

For detailed study, please refer to
https://labuladong.gitee.io/a...

https://houbb.github.io/2020/...

And for this question

Code

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
    }
}

Complexity analysis

Time complexity ：O(n), among n For the size of the array . Just access nums Array again , common n A place .

Spatial complexity ：O(1) , Constant level space overhead .

The second question is Different paths

subject

Ideas

dp

This is the classical lattice model in combinatorics , Its calculation is equivalent to Yang Hui triangle

All are

f(i,j)=f(i−1,j)+f(i,j−1)

Code

func uniquePaths(m int, n int) int {
    // initialization 
    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]
}

Complexity analysis

Time complexity ：O（mn）, To calculate the m*n Matrix number , In the end, I got the second m Xing di n The answer to the column

Spatial complexity ：O（mn）, Get the final answer with a two-dimensional array

meanwhile

Combinatorial mathematics

go Language provides a method to calculate the number of permutations

So we can call this method directly to get the answer

The specific parameters of the method are

The first m,n The number of combinations of items is

So the code is

func uniquePaths(m, n int) int {
    return int(new(big.Int).Binomial(int64(m+n-2), int64(n-1)).Int64())
}