jump game
这道题目，让我第一反应是跳兽问题，但是具体忘记了 ，解法也忘了。
看起来就是可以映射到矩阵链的，于是构建递推方程，中间的k似乎不能等于两个端点，然后单独处理这种可能一次跳过的，循环记住第一重是长度，保证子问题已解出。
小心翼翼码完，发现二维全局变量好像超了空间，除了runtime，于是改heap ，超了空间，后来有人说有greedy算法，我目前还没想到。。。。
class Solution {
public:
int MAX=1000000;
bool canJump(int A[], int n) {
if(n==0) return 0;
int **dp=new int*[n];
for(int i=0;i<n;i++)
dp[i]=new int[n];
for(int i=0;i<=n-1;i++)
dp[i][i]=0;
for(int l=2;l<=n;l++)//chain length
{
for(int s=0;s<=n-1;s++)//start indx
{
int e=s+l-1;
if(e>n-1)
break;
if(A[s]>=l-1)//min 1
dp[s][e]=1;
else
{
int min=MAX;
for(int k=s+1;k<=e-1;k++)
{
if(min>dp[s][k]+dp[k][e])
min=dp[s][k]+dp[k][e];
}
dp[s][e]=min;
}
}
}
int minjump=dp[0][n-1];
for(int i=0;i<n;i++)
delete[] dp[i];
delete[] dp;
if(minjump!=MAX) return true;
else return false;
//return minjump;
}
};
后来还是看了题解，贪心算法没有想到，也不知道怎么和贪心的模板题联系，例如活动安排，普通背包基于排序的，Dijstra Huffman基于选择最小(大)，这里就是用last记录 ret次可以跳到的最大，然后cur则是多跳
一步，ret+1的最远，如果当前遍历的i>last, 说明我已经超过当前最远了，那么需要看是否加一步能跳的更远，如果不能就不可能再往后跳了，否则就更新last为多跳一步，ret也++，但是 感觉还是不很make sense
暂时这么理解了。
int jumpgame(int *a, int n)
{
int last=0,cur=0,ret=0;
for(int i=0;i<n;i++)
{
if(i>last)
{
if(cur==last)
return -1;
last=cur;
ret++;
}
if(cur<i+a[i])
cur=i+a[i];
}
return ret;
}