dp[row, col] = dp[row-1, col] + dp[row, col-1] thôi.
Hôm nọ e xem pv Ngô Quý Đăng HCV IMO thấy có nhắc đến cái problem này, đoạn 3:20Bài hôm nay có thể giải bằng 2 cách: quy hoạch động hoặc dùng công thức toán
- Công thức
dp[row, col] = dp[row-1, col] + dp[row, col-1]thôi.- https://leetcode.com/submissions/detail/761921836/
* Nghĩ hoài không ra, toán không phải là thế mạnh của vozer
xưa đi pvan gặp bài này nhưng đọc cách giải bằng toán không được ưng, lúc đó chưa biết đến quy hoạch động
Vl cái công thức toánBài hôm nay có thể giải bằng 2 cách: quy hoạch động hoặc dùng công thức toán
- Công thức
dp[row, col] = dp[row-1, col] + dp[row, col-1]thôi.- https://leetcode.com/submissions/detail/761921836/
* Nghĩ hoài không ra, toán không phải là thế mạnh của vozer
Lúc print cái dp ra thấy nó có quy luật, nên t đoán là có thể dùng ct toán để giải mà nghĩ k ra nên bỏ qua.Bài hôm nay có thể giải bằng 2 cách: quy hoạch động hoặc dùng công thức toán
- Công thức
dp[row, col] = dp[row-1, col] + dp[row, col-1]thôi.- https://leetcode.com/submissions/detail/761921836/
* Nghĩ hoài không ra, toán không phải là thế mạnh của vozer
tìm công thức toán dễ lắm, quay cái mảng 2 chiều đó 1 góc 45 độ theo chiều kim đồng hồ là ra tam giác pascal àBài hôm nay có thể giải bằng 2 cách: quy hoạch động hoặc dùng công thức toán
- Công thức
dp[row, col] = dp[row-1, col] + dp[row, col-1]thôi.- https://leetcode.com/submissions/detail/761921836/
* Nghĩ hoài không ra, toán không phải là thế mạnh của vozer
int uniquePaths(int m, int n) {
int N = n + m - 2;
int K = std::min(n, m) - 1;
long long res = 1;
for (int i = 1; i <= K; ++i) res = res * N-- / i;
return static_cast<int>(res);
}
Đang ngồi lấy giấy ra định xem công thức toán của bác có đúng ko thìBài hôm nay có thể giải bằng 2 cách: quy hoạch động hoặc dùng công thức toán
- Công thức
dp[row, col] = dp[row-1, col] + dp[row, col-1]thôi.- https://leetcode.com/submissions/detail/761921836/
* Nghĩ hoài không ra, toán không phải là thế mạnh của vozer
class Solution {
public:
int uniquePaths(int m, int n) {
auto rank = m + n - 2;
if (rank < 2)
return 1;
int64_t result = 1;
for (auto i = 1; i<min(m,n);i++){
result *= (rank - i + 1);
result /= i;
}
return (int)result;
}
};2,1,4,5,3 có thể chuyển về cái đồ thịNgoài lề chút có bài này nhờ mấy thím giúp đỡ về ý tưởng ạMình bruteforce thì ra rồi mà không nghĩ ra được ý tưởng nào hay hơn
Code:You are given a string S of length N and an array p representing a permutation of numbers from 1 to N. You shuffle the string as follows: · In one shuffle operation, you replace the character S[i] with S[p[i]]. · You repeatedly do this operation untill you get back S. · Find the number of operations performed. Example: n = 5 s = "ababa" p = 2,1,4,5,3 The string will change as follows: s = babaa s = abaab s = baaba s = abbaa s = baaab s = ababa Therefore, number of shuffling operations performed is 6.
có thể là kiểm tra nếu tất cả các s[i\] trong 1 đồ thị vòng nào mà giống nhau hết thì độ dài của đồ thị vòng đó là 1 
func kthSmallest(matrix [][]int, k int) int {
arrMatrix := make([]int, 0)
for _, rows := range matrix {
for _, value := range rows {
arrMatrix = append(arrMatrix, value)
}
}
sort.Ints(arrMatrix)
return arrMatrix[k-1]
}
bài này n max có 1000 thôi nên O(n) cũng được, dùng sorted list nó đớp lắm tài nguyên thành ra lại chậm
Bài này hay đấy chứThím nào rảnh có thể thử sức bài này, medium mà mình thấy khá chua mà cũng hay
https://leetcode.com/problems/exam-room/
lịt pẹ tưởng ngon ăn code thử đẻ ra corner case tùm lumThím nào rảnh có thể thử sức bài này, medium mà mình thấy khá chua mà cũng hay
https://leetcode.com/problems/exam-room/
mình cũng bị @san1201 dí cho bài này thím, bắn nólịt pẹ tưởng ngon ăn code thử đẻ ra corner case tùm lum
https://leetcode.com/submissions/detail/764128089/
toy xài 1 cái set<pair<int,int>> Q để lưu các khoảng cách sorted từ lớn tới bé, vd {4-9, 0-2, 2-4}, 1 cái map<int, pair<int,int>> M vd -1:0:2, 0:2:4, 2:4:9, 4:9:-1 để biết bên trái bên phải mỗi số p là gì cho leave(p) vd leave(2) biết đường mà xóa 0-2, 2-4 và insert 0-4 lại trong Q, thế đéo nào mà memory 13.40%
Ngựa ngựa làm Log(N) cho cả 2 operators ngồi 3 tiếng debugThím nào rảnh có thể thử sức bài này, medium mà mình thấy khá chua mà cũng hay
https://leetcode.com/problems/exam-room/
(( +1 ban Zayt__
