c語言演算法動態規劃

㈠ 關於c語言動態規劃 資源分配問題演算法的分析

動態規劃演算法一般是n步疊代計算局部最優解，每一步疊代需要計算m個子項，那麼時間復雜度就是O(m*n)。

如果只保存一步疊代的結果，空間復雜度就是O(m)；如果需要保存k步疊代結果，空間復雜度就是O(m*k)。

㈡ 如何用c語言編程實現動態規劃

動態規劃主要是 狀態 & 狀態轉移方程 如果轉移方程寫出來了 程序就自然出來啦

對於這題 dp[i][j] 表示 走到格子 (i,j) 時 的總和最大值 val[i][j] 表示格子 (i, j) 的值

那麼有 dp[i][j] = max( dp[i-1][j] , dp[i][j-1]) + val[i][j];
當然 邊界的時候要特殊考慮一下

for(int i = 1; i <= m ; i++)
for(int j = 1; j <= n; j++)
{
if( i == 1 ) ....;
else if( j == 1 ) ....;
else dp[i][j] = max( dp[i-1][j] , dp[i][j-1]) + val[i][j];
}
最後 dp[m][n] 就是答案啦 ^ ^