帮忙给出DP公式，给出获得DP公式的思维过程，谢谢！

C/C++ code

    Description 一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。 对于给定的n和k(k <= 1000)个加油站位置，编程计算最少加油次数。Input 有多个测试用例。每个测试用例输入数据的第一行有2 个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有k+1 个整数，表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。当输入n，k都是0的时候表示测试结束。Output 将编程计算出的最少加油次数输出，每个测试用例输出一行。如果无法到达目的地，则输出"No Solution"。Sample Input 7 71 2 3 4 5 1 6 65 150 50 0Sample Output 4No Solution

和矩阵的汽车加油一样，感觉不好弄，大家帮忙吧，谢谢大家！

[解决办法]
贪心不可以么？每次走到距离小于等于n且最远的一个加油站
[解决办法]
应该就是1楼所说的贪心就可以了，不用DP。

当走到某地时，剩余油量不足以到下一个加油站时，就需要加满油，逻辑挺简单的。
[解决办法]

探讨

可以的。我想弄明白怎么能写出动态规划，能讲讲么。

[解决办法]
给个简单的贪心例子吧，LZ改一下看看

C# code

using System;namespace csdnTest{    class Program    {        static void Main(string[] args)        {            int[] distance = new int[] { 1, 2, 3, 4, 5, 1, 6, 6 };            int drive = 7, sum = 0, count = 0;            for (int i = 0; i < distance.Length; i++)            {                sum += distance[i];                if (sum > drive)                {                    sum = distance[i];                    count++;                }            }            Console.WriteLine(count);            Console.ReadKey();        }    }}