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] = 0 dp[1] = dp[0]+1 = 1 dp[2] = dp[1]+1 = 2 dp[3] = dp[2]+1 = 3 dp[4] = Min{ dp[4-1*1]+1, dp[4-2*2]+1 } = Min{ dp[3]+1, dp[0]+1 } = 1 dp[5] = Min{ dp[5-1*1]+1, dp[5-2*2]+1 } = Min{ dp[4]+1, dp[1]+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[0].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 …