SIBYL System

just technical blog

Beat my weaknesses: Dynamic Programming

   

Hi there, how about your quarantine life? I’m not bad, because I’m using the time to learn something. Today, I learned Dynamic Programming. In programming, Dynamic Programming is a powerful technique that allows one to solve different types of problems in time O(n^2) or O(n^3) for which a naive approach would take exponential time.

House Robber

https://leetcode.com/problems/house-robber/

  • it’s terrible title.
  • Just do DP.
  • I couldn’t implement the program without using DP array.

House Robber II

https://leetcode.com/problems/house-robber-ii/

  • The graph became to a circle from linear.
  • Calculate with first element removed.
  • Calculate with last element removed.
  • get maximum value from these results.

 - 未分類