AlgoViz
InícioProgramação dinâmica

Programação dinâmica

Subproblemas que se repetem — resolva cada um uma vez e reaproveite sempre.

0/ 65 entendidos · 0%
Explicações
41
Problemas
65
Comece aqui
65 mostrados
  1. FundamentalsSubproblemas que se repetem · uma tabela preenchida uma vezFácil
  2. Solving a Question with DPEstado → recorrência → caso base → ordem → respostaFácil
  3. Climbing Stairsways(i) = ways(i−1) + ways(i−2) · FibonacciFácil
  4. Maximum Subarraycur = máx(nums[i], cur + nums[i]) · KadaneMédio
  5. House Robberdp[i] = máx(dp[i−1], dp[i−2] + nums[i])Médio
  6. Coin Changedp[a] = 1 + mín(dp[a − moeda]) · menor número de moedasMédio
  7. Longest Common SubsequenceDP em grade · casou → diagonal+1, senão máx(acima, esquerda)Médio
  8. Unique PathsDP em grade · dp[i][j] = dp[i−1][j] + dp[i][j−1]Médio
  9. Longest Increasing SubsequencePatience sorting · O(n log n)Médio
  10. Word Breakdp[i] = dá para partir s[0..i) em palavras do dicionário?Médio
  11. Problemas de prática
  12. Frog JumpO melhor entre avançar um ou doisMédio
  13. Frog jump with K distancesO melhor dos k passos anterioresMédio
  14. Maximum sum of non adjacent elementsPegue e pule um, ou pule esteMédio
  15. Ninja's trainingO estado inclui o que foi feito ontemMédio
  16. Grid Unique Paths : DP on GridsCaminhos até aqui = caminhos de cima + caminhos da esquerdaMédio
  17. Unique paths IIUm obstáculo contribui com zero caminhosMédio
  18. Minimum Falling Path SumA melhor das três células acimaMédio
  19. TrianglePreencha de baixo para cimaMédio
  20. Ninja and his FriendsDuas posições, uma linha em comumMédio
  21. Subset sum equal to targetPegar ou pular, indexado pelo alvo restanteDifícil
  22. Partition equal subset sumSoma de subconjunto para metade do totalDifícil
  23. Partition a set into two subsets with minimum absolute sum differenceEncontre todas as somas de subconjunto alcançáveisDifícil
  24. Count subsets with sum KSome os dois ramos em vez de aplicar ORDifícil
  25. Count partitions with given differenceResolva para a soma de um subconjuntoDifícil
  26. Assign CookiesOrdene os dois e case com ganânciaFácil
  27. Minimum CoinsIlimitado: fique na mesma moedaDifícil
  28. Target sumOs sinais viram uma escolha de subconjuntoDifícil
  29. Coin Change 2Moedas no laço externo, senão você conta ordenaçõesDifícil
  30. Unbounded knapsackPegar um item não o consomeDifícil
  31. Rod Cutting ProblemUma mochila ilimitada disfarçadaDifícil
  32. Print Longest Common SubsequencePercorra a tabela de trás para frenteDifícil
  33. Longest common substringZere quando não casarDifícil
  34. Longest palindromic subsequenceA LCS da cadeia com o inverso delaDifícil
  35. Minimum insertions to make string palindromeGuarde o maior núcleo palindrômicoDifícil
  36. Minimum insertions or deletions to convert string A to BTudo que está fora da LCS precisa mudarDifícil
  37. Shortest common supersequenceAs duas cadeias, compartilhando a LCS uma só vezDifícil
  38. Distinct subsequencesCase ou pule o caractere de sDifícil
  39. Edit distanceInserir, apagar ou trocar — fique com o mais baratoDifícil
  40. Wildcard matching'*' consome um caractere ou nenhumDifícil
  41. Best time to buy and sell stockO mais barato até agora, o melhor lucro até agoraMédio
  42. Best time to buy and sell stock IISome cada subidaMédio
  43. Best time to buy and sell stock IIIQuatro estados ao longo do diaMédio
  44. Best time to buy and sell stock IVA máquina de quatro estados, generalizada para kMédio
  45. Best Time to Buy and Sell Stock with CooldownTrês estados: com a ação, vendido, livreMédio
  46. Best time to buy and sell stock with transaction feesCobre a taxa uma vez por transaçãoMédio
  47. Print Longest Increasing SubsequenceGuarde um antecessor junto de cada comprimentoMédio
  48. Largest Divisible SubsetOrdene e depois faça LIS com um teste de divisibilidadeMédio
  49. Longest String ChainOrdene por comprimento e estenda um caractere por vezMédio
  50. Longest Bitonic SubsequenceLIS pela esquerda, LIS pela direitaMédio
  51. Number of Longest Increasing SubsequencesLeve uma contagem junto de cada comprimentoMédio
  52. Matrix chain multiplicationTente todos os pontos de corteDifícil
  53. Minimum cost to cut the stickDP de intervalos sobre as posições de corteDifícil
  54. Burst balloonsEscolha o balão que estoura por últimoDifícil
  55. Different Ways to Evaluate a Boolean ExpressionConte separadamente as formas verdadeiras e as falsasMédio
  56. Palindrome partitioning IICorte onde o prefixo for um palíndromoDifícil
  57. Partition Array for Maximum SumTente todos os tamanhos de grupo que terminam aquiMédio
  58. Maximum Rectangle Area with all 1's|Um histograma por linhaDifícil
  59. Count Square Submatrices with All Ones|Cada célula conta os quadrados que terminam aliFácil
  60. Solving a Question with Dynamic ProgrammingEstado, recorrência, caso base, ordemMédio
  61. Counting BitsReaproveite a resposta da metade do númeroMédio
  62. Decode WaysUm dígito ou dois, se for válidoMédio
  63. Maximal SquareA mesma recorrência, pegando o máximoMédio
  64. Maximum Profit in Job SchedulingOrdene pelo fim e busque binariamente o último trabalho compatívelMédio
  65. Paint HouseO menor custo por cor, para cada casaMédio
  66. Paint House IIAcompanhe as duas melhores cores anterioresMédio