Base case 就是把没有实际意义的状态先设置好，具体可以看你怎么遍历的，没遍历到的都是Base case。
class Solution { public: int maxProfit(int k, vector<int>& prices) { int n=prices.size(); int dp[n+1][k+1][2]; for(int i=0;i<=k;i++){//第0天的情况 dp[0][i][0]=0; dp[0][i][1]=-1e9; } for(int i=0;i<=n;i++){//交易次数是0的情况 dp[i][0][0]=0; dp[i][0][1]=-1e9; } for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]+prices[i-1]); dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i-1]); } } return dp[n][k][0]; } };
class Solution { public: int maxProfit(vector<int>& prices) { int n=prices.size(); int dp[n+1][3]; dp[0][0]=0; dp[0][1]=-1e9; dp[0][2]=-1e9; for(int i=1;i<=n;i++){ dp[i][0]=max(dp[i-1][0],dp[i-1][2]); dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i-1]); dp[i][2]=dp[i-1][1]+prices[i-1]; } return dp[n][0]>dp[n][2]?dp[n][0]:dp[n][2]; } };
class Solution { public: int maxProfit(vector<int>& prices, int fee) { int n=prices.size(); int dp[n+1][2]; dp[0][0]=0; dp[0][1]=-1e9; for(int i=1;i<=n;i++){ dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i-1]-fee); dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i-1]); } return dp[n][0]; } };
