C++ python Mahonian三角四項遞迴公式解Leetcode難題629 K Inverse Pairs Array
Fact 1 is for better writing f(n, k)=\sum_{j=0}^{n-1}f(n-1, k-j)
Leetcode 629. K Inverse Pairs Array解這類的Leetcode難題，先導一導數學式，原先已知有個n項的遞迴公式，雖然可以直接用+DP，但就是慢。有幾招，一招試看能不能用prefix sum，或者先做數學，簡化公式為四項遞迴+DP動態規劃，如此O(nk)解就能完成。
-----
It is known that there is a recursive formula with n terms. Although +DP can be used directly, it is slow. There are a few tricks. One way is to try to see if you can use prefix sum, or do some math first and simplify the formula into four-term recursion + dynamic programming, so that the O(nk) solution can be completed.
[codes on Leetcode]https://leetcode.com/problems/k-inverse-pairs-array/solutions/4632022/4-term-recurrence-mahonian-numbers-dp-o-nk-6-ms-beats-87-36/
[Leetcode playList]https://www.youtube.com/watch?v=KHVXYo7LxZE&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk
[Dynamic Programming Playlist]https://www.youtube.com/watch?v=30yq3fmE6E8&list=PLYRlUBnWnd5K_XYUesV9oc6M9ONXII61T
沒有留言:
張貼留言