AlgoViz
InicioProgramación dinámica

Programación dinámica

Subproblemas solapados: resuelve cada uno una vez y reutilízalo siempre.

0/ 65 entendidos · 0%
Recorridos
41
Problemas
65
Empieza aquí
65 mostrados
  1. FundamentalsSubproblemas solapados · una tabla que rellenas una sola vezFácil
  2. Solving a Question with DPEstado → recurrencia → caso base → orden → respuestaFácil
  3. Climbing Stairsways(i) = ways(i−1) + ways(i−2) · FibonacciFácil
  4. Maximum Subarraycur = máx(nums[i], cur + nums[i]) · KadaneMedia
  5. House Robberdp[i] = máx(dp[i−1], dp[i−2] + nums[i])Media
  6. Coin Changedp[a] = 1 + mín(dp[a − moneda]) · el menor número de monedasMedia
  7. Longest Common SubsequenceDP en cuadrícula · coincide → diagonal+1, si no máx(arriba, izquierda)Media
  8. Unique PathsDP en cuadrícula · dp[i][j] = dp[i−1][j] + dp[i][j−1]Media
  9. Longest Increasing SubsequencePatience sorting · O(n log n)Media
  10. Word Breakdp[i] = ¿se puede partir s[0..i) en palabras del diccionario?Media
  11. Problemas de práctica
  12. Frog JumpLo mejor entre avanzar uno o dosMedia
  13. Frog jump with K distancesLo mejor de los k pasos anterioresMedia
  14. Maximum sum of non adjacent elementsTómalo y sáltate uno, o sáltateloMedia
  15. Ninja's trainingEl estado incluye lo que hiciste ayerMedia
  16. Grid Unique Paths : DP on GridsCaminos hasta aquí = caminos de arriba + caminos de la izquierdaMedia
  17. Unique paths IIUn obstáculo aporta cero caminosMedia
  18. Minimum Falling Path SumLo mejor de las tres celdas de arribaMedia
  19. TriangleRellena hacia arriba desde la baseMedia
  20. Ninja and his FriendsDos posiciones, una fila compartidaMedia
  21. Subset sum equal to targetTomar o saltar, indexado por el objetivo restanteDifícil
  22. Partition equal subset sumSuma de subconjunto para la mitad del totalDifícil
  23. Partition a set into two subsets with minimum absolute sum differenceEncuentra todas las sumas de subconjunto alcanzablesDifícil
  24. Count subsets with sum KSuma las dos ramas en vez de aplicarles ORDifícil
  25. Count partitions with given differenceResuelve para la suma de un subconjuntoDifícil
  26. Assign CookiesOrdena ambos y empareja con avidezFácil
  27. Minimum CoinsIlimitado: quédate en la misma monedaDifícil
  28. Target sumLos signos se convierten en una elección de subconjuntoDifícil
  29. Coin Change 2Las monedas en el bucle exterior, o contarás ordenacionesDifícil
  30. Unbounded knapsackTomar un objeto no lo consumeDifícil
  31. Rod Cutting ProblemUna mochila ilimitada disfrazadaDifícil
  32. Print Longest Common SubsequenceRecorre la tabla hacia atrásDifícil
  33. Longest common substringVuelve a cero cuando no coincidaDifícil
  34. Longest palindromic subsequenceLa LCS de la cadena con su inversaDifícil
  35. Minimum insertions to make string palindromeConserva el núcleo palindrómico más largoDifícil
  36. Minimum insertions or deletions to convert string A to BTodo lo que queda fuera de la LCS tiene que cambiarDifícil
  37. Shortest common supersequenceAmbas cadenas, compartiendo la LCS una sola vezDifícil
  38. Distinct subsequencesEmpareja u omite el carácter de sDifícil
  39. Edit distanceInsertar, borrar o sustituir: quédate con lo más baratoDifícil
  40. Wildcard matching'*' consume un carácter o ningunoDifícil
  41. Best time to buy and sell stockLo más barato hasta ahora, el mejor beneficio hasta ahoraMedia
  42. Best time to buy and sell stock IIRecoge cada subidaMedia
  43. Best time to buy and sell stock IIICuatro estados a lo largo del díaMedia
  44. Best time to buy and sell stock IVLa máquina de cuatro estados, generalizada a kMedia
  45. Best Time to Buy and Sell Stock with CooldownTres estados: con acciones, vendido y libreMedia
  46. Best time to buy and sell stock with transaction feesCobra la comisión una vez por transacciónMedia
  47. Print Longest Increasing SubsequenceGuarda un predecesor junto a cada longitudMedia
  48. Largest Divisible SubsetOrdena y luego aplica LIS con una prueba de divisibilidadMedia
  49. Longest String ChainOrdena por longitud y extiende un carácter cada vezMedia
  50. Longest Bitonic SubsequenceLIS por la izquierda, LIS por la derechaMedia
  51. Number of Longest Increasing SubsequencesLleva un conteo junto a cada longitudMedia
  52. Matrix chain multiplicationPrueba todos los puntos de corteDifícil
  53. Minimum cost to cut the stickDP de intervalos sobre las posiciones de corteDifícil
  54. Burst balloonsElige el globo que se revienta el últimoDifícil
  55. Different Ways to Evaluate a Boolean ExpressionCuenta por separado las formas verdaderas y las falsasMedia
  56. Palindrome partitioning IICorta allí donde el prefijo sea un palíndromoDifícil
  57. Partition Array for Maximum SumPrueba todas las longitudes de grupo que terminan aquíMedia
  58. Maximum Rectangle Area with all 1's|Un histograma por filaDifícil
  59. Count Square Submatrices with All Ones|Cada celda cuenta los cuadrados que terminan ahíFácil
  60. Solving a Question with Dynamic ProgrammingEstado, recurrencia, caso base y ordenMedia
  61. Counting BitsReutiliza la respuesta de la mitad del númeroMedia
  62. Decode WaysUn dígito o dos, si es válidoMedia
  63. Maximal SquareLa misma recurrencia, tomando el máximoMedia
  64. Maximum Profit in Job SchedulingOrdena por el final y busca binariamente el último trabajo compatibleMedia
  65. Paint HouseEl mejor coste por color y por casaMedia
  66. Paint House IISigue los dos mejores colores anterioresMedia