南通企业做网站重庆seo技术

思路：dp

这道题一开始想的时候并不会，但是看到了有些水果可以买也可以不买，所以就想到了选择与不选择的思路。

对于每一个水果，我们都有买和不买的选择，但是我们的第一个水果是一定要买的。然后再往后推导。

用dp[][2]来表示这个状态方程。dp[i][1]表示的就是选择买第i个水果，另外一个状态就是不买了。

但是大家也发现了，不买水果的话，我们还需要知道的一点就是前面是否有买过水果能让当前这个水果不用买呢？这是这道题的核心问题。既然不买，那么肯定就必须是前面买过的水果里有覆盖这个水果的。

这怎么办呢？我们想，既然我们已经到了第i个水果了，证明说前面的水果我们都已经挑选完毕了，我们可以枚举前面j个水果（j<i）的购买情况，而是否覆盖当前的水果，我们就用j+j>=i来表示。为什么呢？第一个j代表我们已经买到当前的水果j了，然后这个水果又可以往后覆盖j个水果让他免费。并且这个>=i是包含我们当前水果的判断。

dp[i][0]=min(dp[i][0],dp[j][1])这就是不选择买当前水果的方程。

好了，我解决最棘手的问题之后，剩下的就好解决了，选择买这个水果那么方程就是：

dp[i][1]=min(dp[i-1][0],dp[i-1][1])+prices[i-1]（这里i是从2开始的）

上代码：

class Solution {
public:int minimumCoins(vector<int>& prices) {int n=prices.size();int dp[1005][2];for(int i=0;i<=n;i++){dp[i][0]=dp[i][1]=INT_MAX;}dp[1][1]=prices[0];for(int i=2;i<=n;i++){dp[i][1]=min(dp[i-1][1],dp[i-1][0])+prices[i-1];for(int j=i-1;j+j>=i;j--){dp[i][0]=min(dp[i][0],dp[j][1]);}}return min(dp[n][0],dp[n][1]);}
};