【移動類DP】數字三角形5

Description

一個數字三角寶塔。

設數字三角形中的數字為絕對值不超過1000的整數。

小K從最頂層走到最底層，每一步可向下或右斜線向下走。

每走過一個節點他會把這個節點的數字加在自己計數器中。

另外他最多隻能向下走k次。

現在小K想知道他到達底層後，計數器中可能的最大的值。

Input

輸入資料的第1行是數字三角形的行數n和能夠沿左斜線向下走的次數k，1<=n<=1000，0<=k<=100。

接下來n行是數字三角形各行中的數字。所有數字都小于1000。

Output

如題

Sample Input

4 2
1
3 2
40 10 1
100 3 2 20
           

Sample Output

47
           

分析

思路一

可以将狀态設計成三維，表示走到目前位置（i，j）時向下走過k步所能走出的最大值。

狀态轉移方程

dp[ i ][ j ][ k ] = max(dp[ i - 1 ][ j - 1 ][ k ], dp[ i - 1 ][ j ][ k - 1 ]) + a[ i ][ j ];

思路二

通過觀察我們會發現，這道題因為有一個向下走的次數限制，有些地方是不可能被走到的。

比如下面這個圖，綠線以下的那幾個點是一定不可能被走到的。

那麼，這個題就變得簡單了。因為不用再管步數的限制，正常轉移就好，時間複雜度O(n ^ 2)。

代碼

#include<bits/stdc++.h>
using namespace std;
int n, k;
int a[1010][1010];
int dp[1010][1010];
int ans = -1e9;
 
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    return x * f;
}
 
int main() {
    n = read(), k = read();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            a[i][j] = read();
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n + 1; j++) {
            dp[i][j] = -1e9;
        }
    }
    dp[1][1] = a[1][1];
    for (int i = 2; i <= n; i++) {
        if (i <= k + 1) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
//              cout << dp[i][j] << " ";
            }
//          cout << endl;
        }
        else {
            for (int j = i - k; j <= i; j++) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
//              cout << dp[i][j] << " ";
            }
//          cout << endl;
        } 
    }
    for (int i = n - k - 1; i <= n; i++) {
        ans = max(ans, dp[n][i]);
    }
    printf("%d", ans);
    return 0;
}