方法一：动态规划

dp[i][j]表示到(i,j)的方法数

  1. package main
  3. /**
  4.  * @Author: yirufeng
  5.  * @Date: 2022/4/28 6:53 下午
  6.  * @Email: yirufeng@foxmail.com
  7.  * @GitHub: https://www.github.com/sivanWu0222
  8.  * @Desc:
  9.  **/
  10. func uniquePaths(m int, n int) int {
  12.     //基本的动态规划
  13.     dp := make([][]int, m)
  14.     for i := 0; i < m; i++ {
  15.         dp[i] = make([]int, n)
  16.     }
  18.     //初始化第一行
  19.     for i := 0; i < n; i++ {
  20.         dp[0][i] = 1
  21.     }
  23.     //初始化第一列
  24.     for i := 0; i < m; i++ {
  25.         dp[i][0] = 1
  26.     }
  28.     for i := 1; i < m; i++ {
  29.         for j := 1; j < n; j++ {
  30.             dp[i][j] = dp[i-1][j] + dp[i][j-1]
  31.         }
  32.     }
  34.     return dp[m-1][n-1]
  35. }

方法二：状态压缩

//方法二：进行状态压缩之后的
func uniquePaths(m int, n int) int {

    ret := make([]int, n)
    for i := 0; i < n; i++ {
        ret[i] = 1
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            ret[j] = ret[j-1] + ret[j]
        }
    }

    return ret[n-1]
}