#include<>
#include<>
#define MAX 99999
int min(int *a, int *b);
int BestJump(int a[], int len, int *dp);
//动态规划 跳跃二
int main()
{
int n;
int *dp;//申请一个动态数组作为表
printf("请输入元素个数：\n");
scanf("%d", &n);
int a[n];
printf("请输入元素：\n");
for(int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
}
printf("跳跃了%d次！", BestJump(a,n,dp));
return 0;
}
int BestJump(int a[], int len, int *dp)
{
if(len <= 1)
{
return 0;
}
dp = (int *)malloc((len+1)*sizeof(int));
dp[0] = 0;//下面三行代码是表格的初始化
for(int i = 1; i < len; ++i)
{
dp[i] = MAX;
}
//从数组下标为一的元素开始遍历
for(int i = 1; i < len; ++i)
{
for(int j = 0; j < i; ++j)//这里之所以要小于i是因为我们每一次求得的dp[i]都是i之前需要跳跃的次数，当时我这里一直不明白，其实是因为我没有弄明白这个问题的算法
{
if(a[j] + j >= i)
{
if(dp[j] + 1 < dp[i])
dp[i] = dp[j] + 1;
// dp[i] = min(&dp[i], &dp[j]+1);
break;
}
}
}
return dp[len -1];
}
int min(int *a, int *b)
{
return ((*a)<(*b)?(*a):(*b));
}
至于为啥是最少即最优问题我想这里面可能有贪心的成分吧，就比如a[0] = 3,他可以跳跃到达a[3],a[2],a[1];