c++算法編程（當當發現校園裏有兩個神奇的樹(分別編號為1,2), 會在夜晚不停的掉落金幣...)

動態規劃題目：記a[i]為第i秒掉下金幣的那棵樹。f[i, k, w]為第i秒正好站在樹k下面並還剩w的移動步數時，在1～i秒獲得的總金幣數量。

那麽f[i, k, w] = max{f[i-1, k, w], ?f[i-1, 3-k, w-1]} +?(a[i] == k); （兩種情況，上壹秒在同壹棵樹下，上壹秒在另壹顆樹下）。

初始條件f[0, k, w] = 0 (對所有的k=1和w=1..W)。簡單的代碼如下

f[0][0][i]?=?0；

for?(int?i?=?0;?i?<=?W;?i++)

f[0][0][i]?=?-100000000；

for?(int?t?=?1;?t?<=?T;?t++)

for?(int?w?=?0;?w?<=?W;?w++)

for?(int?k?=?0;?k?<=?1;?k++)

f[t][k][w]?=?max(f[t-1][k][w],?f[t-1][1-k][w-1])?+?(k?==?a[i]?-1);

int?res?=?0;

for?(int?w?=?0;?w?<=?W;?w++)

for?(int?k?=?0;?k?<?2;?k++)

res?=?max(res,?f[T][k][w]);

printf("%d",?res);