From LI2 Contests Group

Contest 19. Dynamic Programming

• Contest Problems

C. Turtle and Money

Problem: C. Turtle and Money

Solution: GitHub Code

• dp[i][j] 表示從 (0, 0) 走到 (i, j) 的加總最大值
• tar = dp[x][y] - arr[x][y] 就可以知道上一個數值，可能為 dp[x-1][y] 或 dp[x][y-1]

void solve() {
    int n, m;
    cin >> n >> m;

    vector < vector < int > > arr(n, vector < int > (m));
    FOR(i, 0, n){
        FOR(j, 0, m){
            cin >> arr[i][j];
        }
    }

    int offs[2][2] = {{-1, 0}, {0, -1}};

    vector < vector < int > > dp(n, vector < int > (m, 0));
    FOR(i, 0, n){
        FOR(j, 0, m){
            int val = -INT_MAX;
            FOR(k, 0, 2){
                int x = i + offs[k][0];
                int y = j + offs[k][1];
                if(x>=0 and x<n and y>=0 and y<m){
                    val = max(val, dp[x][y]);
                }
            }
            if(val == -INT_MAX){
                val = 0;
            }
            val += arr[i][j];
            dp[i][j] = val;
        }
    }

    cout << dp[n-1][m-1] << endl;

    int x = n-1;
    int y = m-1;
    stack < char > ans;
    while(x>0 or y>0){
        char dir;
        int tar = dp[x][y] - arr[x][y];
        if(x-1>=0 and dp[x-1][y]==tar){
            dir = 'D';
            x--;
        }else if(y-1>=0 and dp[x][y-1]==tar){
            dir = 'R';
            y--;
        }
        ans.push(dir);
    }

    while(!ans.empty()){
        cout << ans.top();
        ans.pop();
    }
}

E. Knight

Problem: E. Knight

Solution: GitHub Code

• dp[i][j] 為走到 (i, j) 的種數

void solve() {
    int n, m;
    cin >> n >> m;

    int offs[2][2] = {{-1, -2}, {-2, -1}};
    vector < vector < int > > dp(n, vector < int > (m, 0));
    dp[0][0] = 1;
    FOR(i, 0, n){
        FOR(j, 0, m){
            FOR(k, 0, 2){
                int x = i + offs[k][0];
                int y = j + offs[k][1];
                if(x>=0 and x<n and y>=0 and y<m){
                    dp[i][j] += dp[x][y];
                }
            }
        }
    }

    cout << dp[n-1][m-1] << endl;
}

I. Levenshtein Distance

Problem: I. Levenshtein Distance

Solution: GitHub Code

• 兩個字串由後往前找 (i, j) ：

  1. 如果 s1[i]==s2[j]: 則可以視 (i+1, j+1) 為相同的答案
  2. 如果不一樣，那麼就找以下三種作法的最小值+1：
     1. Replace: (i+1, j+1)
     2. Delete: (i+1, j)
     3. Insert: (i, j+1)

• 初始化最後一排及最後一列，此狀態問題為字串s1/s2與空字串的差，即為字串s1/s2的長度，因此遞減為0

• 可以參考這支影片

void solve() {
    string s1, s2;
    cin >> s1 >> s2;

    int l1 = s1.size();
    int l2 = s2.size();

    vector < vector < int > > dp(l1+1, vector < int > (l2+1, 0));
    FOR(i, 0, l1+1) dp[i][l2] = l1-i;
    FOR(j, 0, l2+1) dp[l1][j] = l2-j;

    for(int i=l1-1; i>=0; i--){
        for(int j=l2-1; j>=0; j--){
            if(s1[i]==s2[j]){
                dp[i][j] = dp[i+1][j+1];
            }else{
                int val = min(dp[i+1][j], dp[i][j+1]);
                val = min(val, dp[i+1][j+1]);
                dp[i][j] = val + 1;
            }
        }
    }

    cout << dp[0][0] << endl;
}

N. Knapsack Problem

Problem: N. Knapsack Problem

Solution: GitHub Code

• 01 背包問題，只是陣列裡存的是最少物品數量，若為 INT_MAX 則找不到解法
• dp[i][j] 表示前 i 個物品當中，重量剛好為 j 的最少物品數量

void solve() {
    ifstream fcin("input.txt");
    ofstream fcout("output.txt");

    int n, m;
    fcin >> n >> m;

    vector < int > arr(n);
    FOR(i, 0, n) fcin >> arr[i];

    vector < vector < int > > dp(n+1, vector < int > (m+1, INT_MAX));
    FOR(i, 0, n+1) dp[i][0] = 0;

    FOR(i, 1, n+1){
        FOR(j, 1, m+1){
            dp[i][j] = dp[i-1][j];
            if(j-arr[i-1]>=0 and dp[i-1][j-arr[i-1]]!=INT_MAX){
                dp[i][j] = min(dp[i][j], dp[i-1][j-arr[i-1]]+1);
            }
        }
    }

    if(dp[n][m]!=INT_MAX){
        fcout << dp[n][m] << endl;
    }else{
        fcout << 0 << endl;
    }
}

P. Weights

Problem: P. Weights

Solution: GitHub Code

• 要能將重量平均放在兩邊，則每邊重量各別為總重量的一半
• 若總重量的一半為 m ，則可用 01 背包問題求背包最大為 m 時，是否能裝滿

void solve() {
    ifstream fcin("input.txt");
    ofstream fcout("output.txt");

    int n;
    fcin >> n;

    int m = 0;
    vector < int > arr(n);
    FOR(i, 0, n){
        fcin >> arr[i];
        m += arr[i];
    }

    if(m%2==1){
        fcout << "NO" << endl;
        return;
    }
    m /= 2;

    vector < vector < int > > dp(n+1, vector < int > (m+1, 0));
    FOR(i, 0, n+1) dp[i][m] = 0;
    FOR(j, 0, m+1){
        if(j>=arr[0]) dp[0][j] = arr[0];
        else dp[0][j] = 0;
    }

    FOR(i, 1, n){
        FOR(j, 1, m+1){
            dp[i][j] = dp[i-1][j];
            if(j-arr[i-1]>=0){
                dp[i][j] = max(dp[i][j], dp[i-1][j-arr[i-1]]+arr[i-1]);
            }
        }
    }

    if(dp[n-1][m] == m){
        fcout << "YES" << endl;
    }else{
        fcout << "NO" << endl;
    }
}