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. OK, I Understand
 
Top