问题：在众多房屋中获得硬币或能量

Question

我面临一个面试问题，我无法解决它并谷歌它但没有用，这里的问题是（哪种算法适合下面给出的问题）

这条线有很多房子，从0开始编号，用户可以访问。每个房子都有自己的能量供应量和硬币供应量 用户从房子 0 开始旅程。在每个访问过的房子里，用户要么从这所房子中获取全部能量（为了增加自己的能量），要么从这所房子里拿走所有硬币。从编号为 i 的房屋到编号为 i+1 的房屋需要 1 个能量单位，并且不可能跳过其间的任何房屋，这意味着在访问编号为 i 的房屋之前。用户必须首先访问房屋 0,1,2,...,i-1，用户可以在任何房屋结束旅程，因为不需要访问所有房屋。

假设一排有n个房子，第i个房子有house_energy[i]能量和house_coins[i]币，用户以initial_energy能量开始能量，用户最多能收集多少币？总是有非负能量的条件？

n houses
initial_energy = 0
house_energy[]= {2,1,1}
house_coins[] = {11, 5, 7}

Constraints
1 <= n <= 1000
0 <= initial_energy <= 10^14
0 <= house_energy <= 10^3
0 <= house_coins <= 10^3

输出说明

There are 5 houses with energies as 1, 5, 3, 3, 1 respectively and coins as 3, 23, 9, 2, 2 respectively and initial energy as 1. 
The best way to gain maximum coins is to get energy from the first house i.e. 1 and coins from the second and third house that is 23 + 9.
Cannot go any further, since 2 energy was used. The maximum number of coins collected is 32 coins

请找到下面给出的图片，如果有人知道这个想法让我知道，我需要使用 golang 开发这个概念。

第一页 输出

Answer 1

我将继续定义dp[i][e]. dp[i][e]表示我可以收集的最大硬币，如果我从第 i 个索引开始并且有能量 e。

观察：

无论我的初始能量是多少，我都不会需要超过nn 是coins数组大小的地方。证明是直观的。

所以对于每一个，i如果我从能量开始，我会计算我可以收集多少硬币e。我的最终答案将是dp[0][intialEnergy]。

现在dp[n - 1][e] = coins[i]对于 e 的任何值，因为我们不会在最后一个单元格中购买任何能量，因为这不是最佳的。

我现在将开始计算n - 1并一直计算到 0。

在任何情况下，i我们都有 2 个选择，获取能量并继续前进或获取硬币并继续前进。此外，我们知道移动到下一个块会花费我们1额外的能量。照这样说

如果我们使用我们拥有的能量 dp[i][e] = dp[i + 1][min(e + energy[i] - 1, n)];// 我们将限制为 n，因为能量超过 n 是无用的。

如果我们拿硬币：请注意，如果我们拿硬币，我们知道我们只有在那个细胞有能量时才能拿走它们>= 1。所以递归变为：

if(e - 1 >= 0) { dp[i][e] = max(dp[i][e], coins[i] + dp[i + 1][e - 1]); }

如果能量为 0 会怎样。好吧，在这种情况下，我们可以选择购买能量并继续前进（在第一种情况下考虑）或在这种情况下拿硬币并留下来。所以，

if(e == 0) { dp[i][e] = max(dp[i][e], coins[i]); }

显然，我们取了所有 3 种情况的最大值。这是最终的代码

`int getRich（长初始能量，矢量能量，矢量硬币）{

int dp[1001][1001];

int i, e, n = energy.size();

for(i = n - 1; i >= 0; --i) {
    for(e = 0; e <= n; ++e) {
        if(i == n - 1) {
            dp[i][e] = coins[i];
        } else {
            dp[i][e] = dp[i + 1][min(e + energy[i] - 1, n)];
            if(e - 1 >= 0) {
                dp[i][e] = max(dp[i][e], coins[i] + dp[i + 1][e - 1]);
            }
            if(e == 0) {
                dp[i][e] = max(dp[i][e], coins[i]);
            }
        }
    }
}
int ene = min((long)n, initialEnergy);
return dp[0][ene];

}`