Algorithm --- different paths (kotlin)

subject

A robot is in a m x n The top left corner of the grid （ The starting point is marked as “Start” ）.

The robot can only move down or right one step at a time . The robot tries to reach the bottom right corner of the grid （ In the figure below, it is marked as “Finish” ）.

Ask how many different paths there are in total ？

Example ：

Input ：m = 3, n = 2
Output ：3
explain ：
From the top left corner , All in all 3 Path to the bottom right .

1. towards the right -> Down -> Down
2. Down -> Down -> towards the right
3. Down -> towards the right -> Down

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/unique-paths
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Solutions

resolvent

    fun uniquePaths(m: Int, n: Int): Int {
    
        val dp = Array(m) {
     Array(n) {
     0 } }
        dp[0][0] = 1
        for (i in 0 until m) {
    
            for (j in 0 until n) {
    
                if (i == 0 && j ==0) continue
                val left = if (i - 1 >= 0) dp[i - 1][j] else 0
                val top = if (j - 1 >= 0) dp[i][j - 1] else 0
                dp[i][j] = left + top
                println(" $i $j ${
      dp[i][j]}")
            }
        }
        return dp[m - 1][n - 1]
    }

summary

1. The simplest in others' eyes , Up to now, I have no idea . After reading the solution to the question, I know what the idea is .