## Notes on reviewing Dynamic Programming

I believe the topic of Dynamic Programming is a hard part of Algorithm. For this reason, I plan to read the related content in Introduction To Algorithm first and take some notes before I start solving problems in LeetCode. What is Dynamic Programming Dynamic programming typically applies to optimization problems in which we make a …

## Perfect Squares

This in No.279 in LeetCode. The math theory is: dp = 0 dp = dp+1 = 1 dp = dp+1 = 2 dp = dp+1 = 3 dp = Min{ dp[4-1*1]+1, dp[4-2*2]+1 } = Min{ dp+1, dp+1 } = 1 dp = Min{ dp[5-1*1]+1, dp[5-2*2]+1 } = Min{ dp+1, dp+1 } = 2 . . …

## Longest Increasing Subsequence

This No.300 in LeetCode. Here are two approaches for this problem, I will introduce both of them here. Dynamic Programming – O(n^2) The first solution using Dynamic Programming. We will create a one-dimension dp array. We will go over the whole array, and store the numbers of greater number in dp array. class Solution { …

This is No.63 in Leetcode. My original solution is: class Solution { private int path = 0; public int uniquePathsWithObstacles(int[][] obstacleGrid) { // get i and j int i = obstacleGrid.length; int j = obstacleGrid.length; i–; j–; findPath(i, i, path, obstacleGrid); return path; } private void findPath(int i, int j, int path, int[][] obstacleGrid){ // …

## Dynamic Programming

What is Dynamic Programming? Let’s have a look at the definition on Introduction to Algorithm： "Dynamic programming like the divide-and-conquer method, solves problems by combining the solutions to sub-problems. Different from divide-and-conquer, dynamic programming applies when the sub-problems overlap — that is, when sub-problems share sub-sub-problems. A dynamic programming algorithm solves each sub-sub-problems just once …