貪心算法之最少跳躍次數

Description

給定一個非負整數數組，假定你的初始位置為數組第一個位置。數組中的每個元素代表你在那個位置能夠跳躍的最大長度。你的目标是到達最後一個下标位置，并且使用最少的跳躍次數。

Input

輸入一組非負整數數組，數組長度不超過500。

Output

最少經過幾次跳躍，可以到達最後一個位置。

Sample Input

2 3 1 1 4

Sample Output

2

算法思想

每次都周遊目前位置所能到達的位置，跳到數字最大即可

#include<iostream>
using namespace std;

int main()
{
	int a[520], n = 0, k;
	
	// 輸入 
	while(cin >> k)
	{
		char x = cin.get();
		a[n++] = k;
		if(x == '\n')
			break;
	}
	
	int i=0, count = 0;
	
	if(n==1)
	{
		cout << 0 << endl;
		return 0;
	}
		
	while(true)
	{
		//如果目前位置可以直接跳到終點 
		if(i+a[i]>=n-1)
		{
			count++;
			break;
		}
		// 找到目前位置所能跳躍範圍内最大的數 
		int maxn = -1, max_index;
		for(int j=i+1; j<=i+a[i]; j++)
			if(a[j]>maxn)
			{
				maxn = a[j];
				max_index = j;
			}
		i = max_index;  // 跳躍到最合适的位置 
		count++; 		
	} 
	
	cout << count << endl;
	return 0;
}