leetcode.1335. 工作计划的最低难度(dp)

$Descriptiojn$
图片说明

$Solution$
$设dp[i][j]表示第i天完成前j项工作的最低难度$ 。

$转移方程:dp[i][j]=min(dp[i][j],dp[i-1][k]+MAX[k+1][j])$ 。

$Code$

class Solution {
public:
    int MAX[305][305];
    int dp[15][305];
    int minDifficulty(vector<int>& job, int d) {
        int n=job.size();
        if(n<d)return -1;
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++)MAX[i][j]=max(MAX[i][j-1],job[j-1]);
        }
        memset(dp,0x3f3f3f,sizeof(dp));
        dp[0][0]=0;
        for(int i=1;i<=d;i++){
            for(int j=i;j<=n;j++){
                for(int k=i-1;k<j;k++){
                    dp[i][j]=min(dp[i][j],dp[i-1][k]+MAX[k+1][j]);
                }
            }
        }
        return dp[d][n];
    }
};