力扣（122.1049）补7.29

122.买卖股票的最佳时机‖

还是那样，感觉懂了一点，毕竟代码容易懂，又感觉没懂，代码背后的算法的思想还是很模糊。

dp（i）（0）表示在前i天，最终没有股票，

dp（i）（1）表示在经过前i天，最终还有一股。

dp（i）（j）值表示前i天所剩最大现金。

每天有2种情况，交易或不交易。

int maxProfit(int* prices, int pricesSize){

    int **dp=malloc(sizeof(int *)*pricesSize);

    for(int i=0;i

    dp[i]=malloc(sizeof(int)*2);

 

    memset(dp[i],0,sizeof(dp[i]));}

    dp[0][0]=0,dp[0][1]=-prices[0];

    for(int i=1;i

        dp[i][0]=fmax(dp[i-1][0],dp[i-1][1]+prices[i]);

        dp[i][1]=fmax(dp[i-1][1],dp[i-1][0]-prices[i]);

    }

    return dp[pricesSize-1][0];

 

}

1049.最后一块石头的重量‖

不会，看来动态规划没几个星期是搞不好的了。

int lastStoneWeightII(int* stones, int stonesSize){

    int sum=0,sum1;

    for(int i=0;i

    sum+=stones[i];

    sum1=sum/2;

    int **dp=malloc(sizeof(int*)*stonesSize);

    for(int i=0;i

        dp[i]=malloc(sizeof(int)*(sum1+1));

        memset(dp[i],0,sizeof(int)*(sum1+1));

这里又因为初始化的问题，用例有几个没通过。sizeof（dp（i））有时可能有问题。

    }/*int dp[stonesSize][sum1+1];

    memset(dp,0,sizeof(dp));*/

    for(int j=sum1;j>=stones[0];j--)

    dp[0][j]=stones[0];

    for(int i=1;i

        for(int j=1;j<=sum1;j++){

            if(stones[i]>j)

            dp[i][j]=dp[i-1][j];

            else

            dp[i][j]=fmax(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]);

        }

    }

    return sum-2*dp[stonesSize-1][sum1];

 

}