自適應動態規劃

自適應動態規劃是一種針對動態規劃問題的解決方案，它可以針對問題的特定性質自適應調整算法以提高效率。自適應動態規劃的核心思想是將重複計算的子問題存儲起來以避免重複計算，並且根據計算結果逐步優化算法。

一、自適應動態規劃的基本思路

自適應動態規劃的基本思路是，當我們計算一個子問題時，我們會把它的解存儲下來。當下一次對同一個子問題求解時，我們先查看存儲的解是否存在，並且是否可以被重用。如果可以重用，我們直接返回這個解，否則我們需要重新計算它。

int dp(int i)
{
    if(dp[i]!=-1) return dp[i];   //如果已經計算過這個子問題，直接返回結果
    // 計算子問題 dp[i]
    // ...
    dp[i] = result;  // 存儲子問題的解
    return dp[i];   // 返回子問題的解
}

自適應動態規劃的思路與傳統的動態規劃思路類似，不同之處在於，自適應動態規劃每次在計算子問題的同時，會存儲這個子問題的解，避免重複計算。

二、自適應動態規劃的優化策略

自適應動態規劃能夠根據問題的特定性質自適應調整算法以提高效率。以下是自適應動態規劃的一些常見優化策略：

1. 空間優化

傳統的動態規划算法常常需要使用一個二維的數組來存儲問題的狀態，但是這樣會浪費很多空間。自適應動態規劃可以通過僅存儲必要的狀態來實現空間優化。例如，對於一個只有一維狀態的問題，我們可以使用一個一維數組來存儲狀態，而不需要使用二維數組。

int dp(int i)
{
    if(dp[i]!=-1) return dp[i];
    dp[i] = dp(i-1) + dp(i-2);
    return dp[i];
}

2. 剪枝優化

在遞歸式動態規劃中，一些分支可能不是必要的，因此通過剪枝可以減少枝條數量，提高效率。例如，有些子問題顯然不能取得最優解，我們可以通過剪枝減少計算量。

int dp(int i, int j)
{
    if(i>=j) return 0;
    if(dp[i][j]!=-1) return dp[i][j];
    for(int k=i; k<j; k++)
        dp[i][j] = min(dp[i][j], dp(i,k) + dp(k+1,j) + cost[i][k] + cost[k+1][j]);
    return dp[i][j];
}

3. 迭代加深

在樹上的動態規劃問題中，使用迭代加深搜索可以避免不必要的重複計算。迭代加深是一種深度優先遍歷的算法，它每次增大搜索的深度，直到找到解為止。

void dfs(int depth)
{
    if(depth == max_depth) return;
    for(int i=1; i<=n; i++)
    {
        // 計算狀態 dp[depth][i]
        // ...
        dfs(depth+1);   // 繼續搜索
    }
}

4. 狀態壓縮

對於一些二進制狀態的問題，可以使用狀態壓縮來減少計算量。例如，在圖的最短哈密頓路徑問題中，我們可以使用二進制狀態來存儲已經訪問過的節點，從而避免重複計算。

int dp(int state, int i)
{
    if(dp[state][i]!=-1) return dp[state][i];
    for(int j=1; j<=n; j++)
    {
        if((state&(1<<j)) == 0)   // 如果節點 j 沒有被訪問過
        {
            dp[state][i] = min(dp[state][i], dp(state|(1<<j),j)+cost[i][j]);
        }
    }
    return dp[state][i];
}

三、自適應動態規劃的應用

自適應動態規劃已經證明是一個非常有用的工具，它能夠用於解決各種各樣的優化問題，例如最短路徑問題、最長公共子序列問題、背包問題等等。

以下是自適應動態規劃的一些應用案例。

1. 最短路徑問題

對於無向圖或有向圖，我們可以使用動態規劃來計算從一個節點到另一個節點的最短路徑。例如，在下面的代碼中，我們使用 Floyd 算法來計算最短路徑。

const int INF = 0x3f3f3f3f;
int dp[maxn][maxn];
int floyd()
{
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]);
    return dp[1][n];
}

2. 最長公共子序列問題

最長公共子序列問題是指給定兩個字符串 S1 和 S2，求它們的最長公共子序列。我們可以使用動態規劃來解決這個問題。

int dp[maxn][maxn];
int lcs(string s1, string s2)
{
    int n1 = s1.size(), n2 = s2.size();
    for(int i=0; i<=n1; i++)
        for(int j=0; j<=n2; j++)
        {
            if(i==0 || j==0) dp[i][j] = 0;
            else if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    return dp[n1][n2];
}

3. 背包問題

背包問題是指給定一個背包，和一些物品，每個物品都有一個重量和價值，求在不超過背包容量的情況下，能夠裝進背包的最大價值。我們可以使用動態規劃來解決這個問題。

int dp[maxn][maxm];
int knapsack(int m, int n)
{
    for(int i=1; i<=n; i++)
        for(int j=1; j=v[i]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+w[i]);
            else dp[i][j] = dp[i-1][j];
        }
    return dp[n][m];
}

以上是自適應動態規劃的基本思路、優化策略和應用案例。自適應動態規劃是一個非常實用的算法，可以在很多問題中發揮巨大的作用。