本文共 7297 字，大约阅读时间需要 24 分钟。
坐标型动态规划解法
需要确定以下四要素：
- state：f[x]表示从起点走到坐标x
f[x][y]表示从起点走到坐标x,y
- function:研究走到x,y这个点之前的一步
- initialize:起点
- answer：终点
1. leetcode-64. Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Example:
Input:[ [1,3,1], [1,5,1], [4,2,1]]Output: 7Explanation: Because the path 1→3→1→1→1 minimizes the sum.
思路：
1.确定状态f[x][y]为从起点走到x,y的最短路径
2.确定function为f[x][y]=min(f[x-1][y]+f[x][y-1])+A[x][y]
3.初始化：初始化第1行和第一列，因为他们在状态转移时缺少前部依赖
4.终点是f[n-1][m-1]
实现：
class Solution { public int minPathSum(int[][] grid) { int l=grid.length; int w=grid[0].length; int[][] minPath=new int[l][w]; minPath[0][0]=grid[0][0]; for(int i=1;i 空间优化的方法：原地更新坐标
class Solution { public int minPathSum(int[][] grid) { int row = grid.length; int col = grid[0].length; for (int i = 1; i < row; i++) { grid[i][0] = grid[i-1][0] + grid[i][0]; } for (int j = 1; j < col; j++) { grid[0][j] = grid[0][j-1] + grid[0][j]; } for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { grid[i][j] = Math.min(grid[i][j-1], grid[i-1][j]) + grid[i][j]; } } return grid[row-1][col-1]; }}
leetcode 62 unique path
leetcode 63. Unique Paths II
leetcode 120. Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[ [2], [3,4], [6,5,7], [4,1,8,3]]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
递归的解法：
private int minPath;public int minimumTotal4(int[][] triangle) { int minPath=Integer.MAX_VALUE; fun(triangle,0,0,0); return minPath; }//1.递归的第一要素：递归的定义：从0,0出发，走到了(x,y)这个点，不包含(x,y)得到的和是sumprivate void fun(int[][] triangle, int x, int y, int sum) { //2. 递归的出口：走到最后一层的时候 if(x==triangle.length){ minPath=Math.min(minPath, sum); return; } //3.递归的第要素：怎么样变为更小的问题 fun(triangle,x,y+1,sum+triangle[x][y]); fun(triangle,x+1,y+1,sum+triangle[x][y]);} 两种思路（动态规划）：
一、自底向上
1.确定状态f[x][y]为从底部走到x,y的最短路径
2.确定function为f[x][y]=min(f[x+1][y]，f[x+1][y+1]) + A[x][y]
3.初始化：初始化三角形的最后一行，因为他们在状态转移时缺少前部依赖（循环时，从倒数第2行开始向第1行遍历，为每一行的每个值计算可能的最小值）
4.终点是f[0][0]
二、自顶向下
1.确定状态f[x][y]为从0,0走到x,y的最短路径
2.确定function为f[x][y]=min( f[x-1][y-1]，f[x-1][y]) + A[x][y]
3.初始化：初始化三角形的最左边和最右边，因为一个元素只有左上和右上有值是才满足公式的计算，但是最左边的元素没有左上的依赖，最右边一行没有右上的依赖）
4.终点是最后一行，我们需要求出最后一行所有元素的最小值，才能获得最小的路径和
实现1：自底向上
class Solution { public int minimumTotal(List > triangle) { int m=triangle.size();//行数 int[][] dp=new int[m][m]; for(int i=0;i =0; i--) { for (int j = 0; j <=i; j++) { dp[i][j]=Math.min(dp[i+1][j], dp[i+1][j+1])+triangle.get(i).get(j); } } return dp[0][0]; }}
实现2：自顶向下
class Solution { public int minimumTotal(List > triangle) { int m=triangle.size(); int[][] dp=new int[m][m]; //初始化 dp[0][0]=triangle.get(0).get(0); for (int i = 1; i < m; i++) { dp[i][0]=dp[i-1][0]+triangle.get(i).get(0); dp[i][i]=dp[i-1][i-1]+triangle.get(i).get(i); } //从上到下遍历 for(int i=1;i
空间优化：
因为每行只会存在一个最小值，因此，只需要用一个一维数组存储之前遍历过得
每一行的可能最小值即可，到下一行的时候，直接在上一行基础上更新即可。public int minimumTotal(List
> triangle) { int[] dp=new int[triangle.size()+1]; for (int i =triangle.size()-1; i>=0; i--) { for (int j = 0; j <=i; j++) { dp[j]=Math.min(dp[j], dp[j+1])+triangle.get(i).get(j); } }return dp[0];}
leetcode 55. Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
Input: [2,3,1,1,4]Output: trueExplanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4]Output: falseExplanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
解题思路：
思路1：
1.确定状态dp[i]表示从0索引出发，到达下标为i的位置时剩余的步数。
如果到达一个位置，dp[i]>=0,表示可以到达i位置。dp[i]<0,则说明到达i位置时剩余步数为负数，直接返回false；
2.确定function为dp[i]=max(dp[i-1],nums[i-1])-1;
3.初始化：初始化dp[0]=nums[0];
4.终点是最后dp[dp.length-1]是否大于0；
实现1：
class Solution { public boolean canJump(int[] nums) { int[] dp=new int[nums.length]; dp[0]=nums[0]; for(int i=1;i 思路2：（常规dp思路，时间很长）
1.确定状态dp[i]表示从0索引出发，是否可以到达i处，可以，则，dp[i]=true,否则dp[i]=false。
2.确定function为:如果nums[i]>=i-j,就是可以跳跃的值大于两点之间的距离，则dp[i]=true；表示可以从j跳跃到i处；
3.初始化：初始化dp[0]=true;
4.终点是最后dp[dp.length-1]；
实现2：
class Solution { public boolean canJump(int[] nums) { boolean[] dp=new boolean[nums.length]; dp[0]=true; for(int i=1;i =i-j){ dp[i]=true; } } } return dp[dp.length-1]; }} 思路3：贪婪的思想（最优解）
计算出某个点能够跳出的最大距离（当前的最大值和（当前点+能跳出的最大距离）的较大的值），如果能跳出的最大距离大于最后一个点的位置，那么返回true，能到达；如果到达当前点后，不能在往后跳，那么不能达到最后点，返回false。
class Solution { public boolean canJump(int[] nums) { if(nums.length<1) return false; if(nums.length==1) return true; int max=0;//记录当前点能到达的最大位置 for(int i=0;i =nums.length-1){ return true; } } return false; }}
leetcode 45. Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]Output: 2Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
思路1：动态规划（时间复杂度 o(n^2）会超时
1.确定状态dp[i]表示从0索引出发，到达下标为i的位置时跳的最少次数。
2.确定function为dp[i]=min(dp[i],dp[j])+1;
3.初始化：初始化dp[0]=0;(trick，将1以后的dp中的值初始化为最大值，然后和后面的结果比小，更新dp[i])
4.终点是最后dp[dp.length-1]存储的是到达最后一个下标需要跳的最少步数；
class Solution { public int jump(int[] nums) { int[] dp=new int[nums.length]; dp[0]=0; for(int i=1;i =i-j&&dp[j]!=Integer.MAX_VALUE){ dp[i]=Math.min(dp[i],dp[j]+1); } } } return dp[dp.length-1]; }} 思路二：贪婪算法
为了较快的跳到末尾，我们想知道每一步能跳的范围，这里贪婪并不是要在能跳的范围中选跳力最远的那个位置，因为这样选下来不一定是最优解，这么一说感觉又有点不像贪婪算法了。我们这里贪的是一个能到达的最远范围，我们遍历当前跳跃能到的所有位置，然后根据该位置上的跳力来预测下一步能跳到的最远距离，贪出一个最远的范围，一旦当这个范围到达末尾时，当前所用的步数一定是最小步数。
我们需要两个变量cur和pre分别来保存当前的能到达的最远位置和之前能到达的最远位置，只要cur未达到最后一个位置则循环继续，pre先赋值为cur的值，表示上一次循环后能到达的最远位置，如果当前位置i小于等于pre，说明还是在上一跳能到达的范围内，我们根据当前位置加跳力来更新cur，更新cur的方法是比较当前的cur和i + A[i]之中的较大值，如果题目中未说明是否能到达末尾，我们还可以判断此时pre和cur是否相等，如果相等说明cur没有更新，即无法到达末尾位置，返回-1。
class Solution { public int jump(int[] nums) { int step=0,n=nums.length; int last=0;//前一次能跳到的最远位置 int curr=0;//当前能跳到的最远位置 //要cur未达到最后一个位置则循环继续 for(int i=0;i =n-1){ break; } } } return step; }}
参考：
（这个写的太好了）
转载地址：http://lldgj.baihongyu.com/