按顺序刷确实效率太低了，今天开始要按顺序的同时也按标题来了，全面加油！这种应该以后会更多直接总结题解了，自我学习用，全靠大佬，贴贴！！含45、55、62、63
CP55 跳跃游戏
题目描述：
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
题解：
class Solution {
public:bool canJump(vector<int>& nums) {int n = nums.size();int rightmost = 0;for (int i = 0; i < n; ++i) {if (i <= rightmost) {rightmost = max(rightmost, i + nums[i]);if (rightmost >= n - 1) {return true;}}}return false;}
};
大佬！：
按这个思路去写，结果超时...我的问题在于，本题需要的是最后一个格子可不可以，我们只需要找到每次跳得最远得地方，我这里定义了一个数组tmp存储每一个地方能不能被跳到，但是这是完全没有用得，更远得能被跳到，那后面得一定可以跳到，无需维护这个数组，只需要记录最远可以跳到得地方。
//我写的超时破代码
class Solution {
public:bool canJump(vector<int>& nums) {int length=nums.size();vector<bool> tmp(length);tmp[0]=true;for(int i=0;i<length;i++){if(tmp[i]==true){int n=nums[i];for(int j=1;j<=n;j++){if(i+j<length){tmp[i+j]=true;}}}}return tmp[length-1];}
};//大佬代码
class Solution {
public:bool canJump(vector<int>& nums) {int k = 0;for (int i = 0; i < nums.size(); i++) {if (i > k) return false;k = max(k, i + nums[i]);}return true;}
};
CP45 跳跃游戏II
题目描述：
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处：0 <= j <= nums[i] 且 i + j < n。返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。注：题目保证可以到达 nums[n-1]
学习记录：
有了第一题的想法，我们只需要不断判断每次的最小步数就行了，初步想法是定义一个储存最小步数的数组，然后不断更新。一道典型的动态规划
//我的思路
class Solution {
public:int jump(vector<int>& nums) {int length=nums.size();vector<int> tmp(length);//存储最少跳数 for(int i=0;i<length;i++) tmp[i]=length;tmp[0]=0;for(int i=0;i<length;i++){int n=nums[i];for(int j=1;j<=n;j++){if(i+j<length){tmp[i+j]=min(tmp[i+j],tmp[i]+1);//这里第一次写成tmp[i]+j了，但是每次只需要加1跳就行}}}return tmp[length-1];}
};题解：
1.正向分析法
其实我们也用了正向分析法，但是正如第一题提到的问题，所有后面能到达的前面也能，同理不用多维护一个数组，在本题，最后一个点一定能到，也就是说这个数组中所有点都是能到的。所以我每次只需要：我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。比我们的方案难理解一点，maxPos:目前能跳到的最远位置；end：上次可跳跃的右边界
class Solution {
public:int jump(vector<int>& nums) {int maxPos = 0, n = nums.size(), end = 0, step = 0;for (int i = 0; i < n - 1; ++i) {maxPos = max(maxPos, i + nums[i]);if (i == end) {end = maxPos;++step;}}return step;}
};2.反向分析法
C++实现超时间了，就学习一下思想，给出java实现的代码
class Solution {public int jump(int[] nums) {int position = nums.length - 1;int steps = 0;while (position > 0) {for (int i = 0; i < position; i++) {if (i + nums[i] >= position) {position = i;steps++;break;}}}return steps;}
}
CP62 不同路径
题目描述：
学习记录：
典型动态规划，维护一个数组，记录路径数即可。
class Solution {
public:int uniquePaths(int m, int n) {int tmp[m][n];for(int i=0;i<m;i++){tmp[i][0]=1;}for(int j=0;j<n;j++){tmp[0][j]=1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){tmp[i][j]=tmp[i-1][j]+tmp[i][j-1];}}return tmp[m-1][n-1];}
};题解：
除了上述方法，还有一种
python中存在API：
def uniquePaths(self, m: int, n: int) -> int:return int(math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1))作者：powcai
CP63 不同路径II
题目描述：
学习记录：
和上述思路一样，只是多加了一个判断，如果有石头就不能走，没啥好说的，写
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m=obstacleGrid.size();int n=obstacleGrid[0].size();int tmp[m][n];int flag=1;for(int i=0;i<m;i++){if(obstacleGrid[i][0]==1) flag=0;if(flag) tmp[i][0]=1;else tmp[i][0]=0;}flag=1;for(int j=0;j<n;j++){if(obstacleGrid[0][j]==1) flag=0;if(flag) tmp[0][j]=1;else tmp[0][j]=0;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){tmp[i][j]=tmp[i-1][j]+tmp[i][j-1];if(obstacleGrid[i][j]==1) tmp[i][j]=0;}}return tmp[m-1][n-1];}
};注：定义可以这样定义：vector<vector<int>> tmp(m,vector<int>(n));
PS：
由于leetcode比较智能允许int t[m][n]这种形式，但是VS2010不行，需要方法如下：
#include <iostream>
#include <string>
#include <iomanip>
using namespace std;void find(int m,int n)
{int *m1=new int [m];for(int i=0;i<m;i++)m1[i]=0;cout<<"m1: "<<m1[0]<<endl;delete m1;int **m2=new int* [m];for(int i=0;i<m;i++)m2[i]=new int [n];for(int i=0;i<m;i++)for(int j=0;j<n;j++)m2[i][j]=1;cout<<"m2: "<<m2[0][0]<<endl;for(int i=0;i<m;i++) delete m2[i];
}int main()
{int m=2;int n=3;find(m,n);system("pause");return 0;
}
