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 . . …

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 …