Dynamic Programming Demystified: How AI Helps You See the Pattern
Dynamic Programming (DP) intimidates even seasoned engineers. With the right lens, it’s just optimal substructure + overlapping subproblems turned into code. In this talk, we start from a brute-force recursive baseline, surface the recurrence, convert it to memoization and tabulation, and connect it to real systems (resource allocation, routing, caching). Along the way you’ll see how to use AI tools (ChatGPT, Copilot) to propose recurrences, generate edge cases, and draft tests—while you retain ownership of correctness and complexity. Expect pragmatic patterns you can reuse in interviews and production.
Why Now
- DP = #1 fear topic in interviews.
- Used in systems: caching, routing, scheduling.
- 55% faster with Copilot, but needs guardrails.
- AI adoption is surging — structure required.
Key Framework
- Find optimal substructure.
- Spot overlapping subproblems.
- Start brute force → derive recurrence.
- Memoization → tabulation.
- Compare vs. greedy & divide-and-conquer.
- Use AI for tests & recurrences, not correctness.
Core Content
- Coin Change: brute force → DP; greedy fails in non-canonical coins.
- 0/1 Knapsack: DP works, greedy fails; fractional knapsack = greedy.
- LIS: O(n²) DP vs. O(n log n) patience method.
- Graphs: shortest path as DP on DAGs.
- AI Demos: recurrence suggestion, edge-case generation.
Learning Outcomes
- Know when a problem is DP-worthy.
- Build recurrence → memoization → tabulation.
- Decide Greedy vs DP confidently.
- Apply AI prompts safely (tests, refactors).
- Map DP to real-world systems.
About Rohit Bhardwaj
Rohit Bhardwaj is a Director of Architecture working at Salesforce. Rohit has extensive experience architecting multi-tenant cloud-native solutions in Resilient Microservices Service-Oriented architectures using AWS Stack. In addition, Rohit has a proven ability in designing solutions and executing and delivering transformational programs that reduce costs and increase efficiencies.
As a trusted advisor, leader, and collaborator, Rohit applies problem resolution, analytical, and operational skills to all initiatives and develops strategic requirements and solution analysis through all stages of the project life cycle and product readiness to execution.
Rohit excels in designing scalable cloud microservice architectures using Spring Boot and Netflix OSS technologies using AWS and Google clouds. As a Security Ninja, Rohit looks for ways to resolve application security vulnerabilities using ethical hacking and threat modeling. Rohit is excited about architecting cloud technologies using Dockers, REDIS, NGINX, RightScale, RabbitMQ, Apigee, Azul Zing, Actuate BIRT reporting, Chef, Splunk, Rest-Assured, SoapUI, Dynatrace, and EnterpriseDB. In addition, Rohit has developed lambda architecture solutions using Apache Spark, Cassandra, and Camel for real-time analytics and integration projects.
Rohit has done MBA from Babson College in Corporate Entrepreneurship, Masters in Computer Science from Boston University and Harvard University. Rohit is a regular speaker at No Fluff Just Stuff, UberConf, RichWeb, GIDS, and other international conferences.
Rohit loves to connect on http://www.productivecloudinnovation.com.
http://linkedin.com/in/rohit-bhardwaj-cloud or using Twitter at rbhardwaj1.