给一个N * K的数组days,days[i][j]表示第j天能在第i个城市休息的天数,每天能选一个城市休息,不过有些城市之间不能跳转,问最多能休息多少天。优化问题,能根据天数分成K个子问题,action为从上一天中选一个城市跳到另一个(可能一样的)城市,受限于从上个城市到这个城市的跳转能否成功。因此dp以天数和所在城市为状态,里头存在第i天在j城市累计最大休息天数。
class Solution {
public:
int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {
const int N = days.size(), K = days[0].size();
vector<vector<int>> dp(K, vector<int>(N, -1));
dp[0][0] = days[0][0];
for (int j = 1; j < N; ++j) {
if (flights[0][j] == 0) continue;
dp[0][j] = days[j][0];
}
for (int i = 1; i < K; ++i) {
for (int j = 0; j < N; ++j) {
for (int k = 0; k < N; ++k) {
if (dp[i - 1][k] == -1 || k != j && flights[k][j] == 0) continue;
dp[i][j] = max(dp[i][j], dp[i - 1][k] + days[j][i]);
}
}
}
int res = 0;
for (int j = 0; j < N; ++j) {
res = max(res, dp[K - 1][j]);
}
return res;
}
};