這是來自 LeetCode https://leetcode.com/problems/unique-paths/的唯一路徑問題。
mxn 網格上有一個機器人。機器人最初位于左上角（即grid[0][0]）。機器人試圖移動到右下角（即grid[m - 1][n - 1]）。機器人只能在任何時間點向下或向右移動。
給定兩個整數 m 和 n，回傳機器人可以到達右下角的可能唯一路徑的數量。
這是來自 tutorialcup 的回溯解決方案https://www.tutorialcup.com/leetcode-solutions/unique-paths-leetcode-solution.htm
import java.util.*;
import java.lang.*;
import java.io.*;
class Solution {
public static int uniquePaths(int m, int n) {
if(m == 1 || n == 1)
return 1;
return uniquePaths(m-1, n) uniquePaths(m, n-1);
}
public static void main(String[] args){
System.out.print(uniquePaths(2,2));
}
}
最差的時間復雜度在 wbesite 中提到為 O(2^max(m,n))。對我來說它看起來不正確。
我認為在每個遞回步驟中有 m*n 個可能性減少一個。
T(mn) = T(mn-1) T(mn-1)
= 2 * T(mn-1)
= 2^mn
所以最壞的時間復雜度是 O(2^mn)。讓我知道我的計算是否正確或遺漏了什么
uj5u.com熱心網友回復：
我認為在每個遞回步驟中有 m*n 個可能性減少一個。
不，它在每一步中減少n或m 。所以：
T(mn) = T(m(n-1)) T((m-1)n) 1
這反映了您的遞回呼叫：兩個引數的乘積（傳遞給遞回呼叫）表示剩余問題空間的大小。
為了計算時間復雜度，添加常數項很重要，因為函式的每次呼叫都代表作業/時間。
此外，使用這種表示法，相同但來自不同網格大小的產品之間的區別消失了。您應該將 2 個維度分開：
T(m, n) = T(m, n-1) T(m-1, n) 1
T(m, 1) = 1
T(1, n) = 1
基本情況表示只剩下 1 列或 1 行的情況，然后機器人只能沿一個方向移動——通過一條路徑。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/411534.html
標籤：