兩個定義不同的函式。
funcA:
a = a - 2;
b = b - 1;
funcB:
a = a - 1;
b = b - 2;
我們的目標是在 a = 0 和 時獲得操作次數b = 0；
樣本輸入： a = 4, b = 2
call funcA:
a become 2, b become 1;
again call funcA
a become 0, b become 0;
執行的操作總數2 0 = 2因此回傳2；
示例輸入 2： a = 3, b = 3
call funcA:
a become 1, b become 2;
call funcB
a become 0, b become 0;
執行的操作總數1 1 = 2因此回傳2；
uj5u.com熱心網友回復：
讓我們從特殊情況開始：
- 如果
a < 0或b < 0我們沒有解決方案 - 如果
a = 0與b <> 0或a <> 0和b = 0我們有沒有解決辦法 - 如果
a > 2 * b或b > 2 * a我們沒有解決方案
如果我們使用funcA x時間和funcB y時間并0從兩者中 得到a，b我們就可以寫
a - 2 * x - y = 0
b - 2 * y - x = 0
讓我們為x和求解這個線性方程組y：
2 * x y = a
2 * y x = b
解決辦法是
x = (2 * a - b) / 3
y = (2 * b - a) / 3
因此，如果我們有一個整數的解決方案x和y我們應該執行funcA x倍，funcB y倍
代碼（Java）：
public static int Solve(int a, int b) {
// beware integer overflow! we use long in case a = 2_000_000_000 provided
long x = (2L * a - b) / 3;
long y = (2L * b - a) / 3;
return ((x >= 0 && y >= 0 && (2L * b - a) % 3 == 0 && (2L * a - b) % 3 == 0))
? (int)(x y)
: -1; // impossible
}
可以看出，我們有一個具有O(1)時間和空間復雜度的直接解決方案；不需要動態規劃
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/350523.html
上一篇：如何在沒有昂貴的預計算的情況下以恒定速度沿著貝塞爾曲線移動？
下一篇：比T(n)高的大Oh符號