我正在尝试编写一个解决方案,通过一个数组找到最便宜的可能路径,并将整数值存储为游戏位置 . 这个想法是从第一个索引到最后一个索引,并根据您决定“停止”的索引产生最便宜的成本 . 您可以从您所在的位置移动到下一个索引,也可以将该索引跳转到下一个索引(ind 1 vs ind 2),直到到达结尾 .
我下面的内容是返回一个大的负整数,这显然是非常错误的 . 我相当肯定它与我如何控制当前位置有关,并且我很容易迭代地做,但递归地证明是困难的 . It must be done recursively 有什么想法让我走上正确的道路?
#include "stdafx.h"
#include <iostream>
#include <array>
using namespace std;
const int GAMEBOARD_SIZE = 6;
int DetermineCheapestPath(int gameBoard[], int lowInd, int highInd, int currentLocation);
int main()
{
int gameBoard[GAMEBOARD_SIZE] = { 0,3,80,6,57,10 };
cout << "The cheapest possible path for this board is " << DetermineCheapestPath(gameBoard, 0, GAMEBOARD_SIZE - 1, 0) << endl;
return 0;
}
int DetermineCheapestPath(int gameBoard[], int lowInd, int highInd, int currentLocation)
{
int lastValue;
int currentValue;
//base case
if (lowInd == highInd)
{
currentLocation -= 1;
return gameBoard[highInd];
}
else
{
lastValue = DetermineCheapestPath(gameBoard, lowInd + 1, highInd, currentLocation + 1);
if (gameBoard[currentLocation] > gameBoard[currentLocation - 1] && currentLocation != 0 && lowInd != 0)
{
currentValue = gameBoard[currentLocation - 1];
currentLocation -= 2;
return lastValue + currentValue;
}
else if (gameBoard[currentLocation] < gameBoard[currentLocation - 1] && currentLocation != 0 && lowInd != 0)
{
currentValue = gameBoard[currentLocation];
currentLocation -= 1;
return lastValue + currentValue;
}
else
{
return lastValue + gameBoard[currentLocation];
}
}
}