leetcode

324. Wiggle Sort II

leetcode

Posted by chl on August 7, 2019

题目

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

start |* —|—

  • *
  • | dest

    题意

    走网格，从左上角走到右下角，只能向下或向右走，问一共有多少条路径可以到达。

    例子

    Example 1:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

  1. Right -> Right -> Down
  2. Right -> Down -> Right
  3. Down -> Right -> Right

题解

很典型的动态规划问题，状态转移方程为f(x,y)=f(x+1,y)+f(x,y+1)表示任意一个位置到达右下角的所有路径由右边一个格子和下边格子的所有路径的和。
从上完下分析问题，分析完后，从下往上解决问题，这里可以将出现过结果保存到一个数组中，避免重复计算

代码

var N,M int
var memory [][]int
func uniquePaths(m int, n int) int {
    M=m
    N=n
    if m==0 || n==0{
        return 0
    }
    memory = make([][]int,n)
    for i,_:=range memory{
        memory[i]=make([]int,m)
        for j:=0;j<m;j++{
            memory[i][j]=-1
        }
    }
    return Paths(1,1)
}

func Paths(m int,n int)int{
    if m>M{
        return 0
    }
    if n>N{
        return 0
    }
    
    if m==M&&n!=N{
        return 1
    }
    
    if n==N&&m!=M{
        return 1
    }
    
    if n==N&&m==M{
        return 1
    }
    
    if memory[n][m]!=-1{
        return memory[n][m]
    }
    memory[n][m]=Paths(m+1,n)+Paths(m,n+1)
    return memory[n][m]
    
}

总结

做过类似的题目，而且该题本身不难，找出状态转方程后，还需要注意效率问题，使用一个记忆数组来存储计算过的结果，避免重复计算。

非递归做法

func uniquePaths(m int, n int) int {
    var memory [][]int
    if m==0 || n==0{
        return 0
    }
    memory = make([][]int,n+1)
    for i,_:=range memory{
        memory[i]=make([]int,m+1)
        for j:=0;j<m;j++{
            memory[i][j]=-1
        }
    }
    for i:=n;i>=1;i--{
        for j:=m;j>=1;j--{
            if i==n{
                memory[i][j]=1
            }else if j==m{
                memory[i][j]=1
            }else {
                memory[i][j]=memory[i+1][j]+memory[i][j+1]
            }
        }
    }
    return memory[1][1]
}