一個(gè)有名的按摩師會(huì)收到源源不斷的預(yù)約請(qǐng)求，每個(gè)預(yù)約都可以選擇接或不接抹锄。在每次預(yù)約服務(wù)之間要有休息時(shí)間藻雌，因此她不能接受相鄰的預(yù)約。給定一個(gè)預(yù)約請(qǐng)求序列吨掌，替按摩師找到最優(yōu)的預(yù)約集合（總預(yù)約時(shí)間最長(zhǎng)）半抱，返回總的分鐘數(shù)。
輸入：[1,2,3,1]
輸出：4
解釋?zhuān)?/b>選擇 1 號(hào)預(yù)約和 3 號(hào)預(yù)約膜宋，總時(shí)長(zhǎng) = 1 + 3 = 4
輸入：[2,7,9,3,1]
輸出：12
解釋?zhuān)?/b>選擇 1 號(hào)預(yù)約窿侈、 3 號(hào)預(yù)約和 5 號(hào)預(yù)約，總時(shí)長(zhǎng) = 2 + 9 + 1 = 12秋茫。
解法：
動(dòng)態(tài)規(guī)劃：第 i 天的選擇只有接受預(yù)約和不接受兩種史简，而這種選擇是受前一天的選擇所制約；假如昨天沒(méi)有選擇肛著，那么今天就可以接受預(yù)約或不接受圆兵，若昨天選擇了，則今天不能接受預(yù)約枢贿。所以可以采用動(dòng)態(tài)規(guī)劃殉农，今天如果服務(wù)的話(huà)，最大服務(wù)時(shí)間是昨天不選擇服務(wù)的最大服務(wù)時(shí)間 + 今天的服務(wù)時(shí)間局荚；假如今天不服務(wù)超凳，那么最大服務(wù)時(shí)間就是昨天不服務(wù)或昨天服務(wù)這兩個(gè)值的最大值愈污。所以可以設(shè)置數(shù)組d[0][i]表示第i天不服務(wù)的最大服務(wù)時(shí)間，d[1][i]則表示第i天服務(wù)轮傍。
空間優(yōu)化：因?yàn)槿绻?i 天服務(wù)的話(huà)暂雹，那么第 i - 1 天必定不能服務(wù)，所以最大服務(wù)時(shí)間d[ i ] = d[ i - 2 ] + nums[ i ],
如果第 i 天不服務(wù)的話(huà)金麸，那么d[ i ] = d [ i - 1] ,所以綜上 d [ i ] = max (?d[ i - 2 ] + nums[ i ] ,?d [ i - 1] )
