• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Mar 23rd, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. 1. Max Sum 1D
2. 5
3. arr[i] 1 3 2 -10 5
4. dp[i] 1 4 6 -4 5
5. O(N)
6.
7. dp[i] = totalan maksimal subsegment yg ujung kanannya indeks i
8. dp[i] = max(dp[i - 1] + arr[i], arr[i])
9.
10. 2. Prefix Sum
11. dp[i] = total semua bilangan dari indeks 0 - indeks i
12. arr[i] 1 3 2 -10 5
13. dp[i] 1 4 6 -4 1
14. dp[j] - dp[i - 1]
15.
16. 3. Max Sum 2D
17. O((N^2).M)
18. 1 2 3
19. 4 5 6
20. 7 8 9
21.
22. 1 2 3
23. 5 7 9
24. 12 15 18
25.
26.
27.
28. -5 10 10
29. 4 -5 -5
30. 6 -5 1
31.
32. -5 10 10
33. -5 10 20
34.
35. - Prefix Sum setiap kolom
36. - Algoritma Max Sum 1D
37.
38. 4. LIS
39. O(N^2)
40. dp[i] = subsequence terpanjang jika i menjadi ujung kanan sequencenya
41. dp[i] = (1 <= j < i) max(dp[j], arr[j] < arr[i]) + 1
42. 3 7 4 5
43. 1 2 2 3
44.
45. 5. Coin Change
46. dp[i] = koin minimal penukaran sebesar i
47. dp[i] = 1 <= j <= n, min(dp[i - coin[j]]) + 1. i >= coin[j]
48. dp[0] = 0
49.
50. 6. Knapsack 0-1
51. O(NM)
52. N = banyak barang
53. M = bobot tas
54. dp[i][j] = nilai maksimal jika barangnya ada sebanyak i (1 - i) bobot yang tersisa sebesar j
55. dp[i][j] = max(dp[i - 1][j - W[i]] + V[i], dp[i - 1][j]), j >= W[i]
56. dp[1][0] = 0;
57. dp[1][j] = V[1] -> j >= W[1]
58.
59. 7. MCM (Matrix Chain Multiplication)
60. dp[i][i] = 0
61. dp[i][j] = proses minimal utk mngalikan matriks ke - i sampai matriks ke - j
62. dp[i][j] = i <= k < j, min(dp[i][k] + dp[k + 1][j] + arr[i] * arr[k + 1] * arr[j + 1])
63.
64. N buah matrix
65. N + 1 bilangan
66. 3
67. 1 2 3 4
68. 1x2
69. 2x3
70. 3x4
71. axb
72. bxc
73. axbxc
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top