HihoCoder – 1037 数字三角形 基础dp、朴素dp

数字三角形 基础dp、朴素dp

Source

HihoCoder - 1037

My Solution

题意：dp基础题，给出一个数字三角形，求一条从顶到底的路径，路径权值和的最大值。

基础dp、朴素dp

复习下dp基础知识，

动态规划的一个核心概念在于不去计算已经计算的东西，不去计算不需要的东西，即"取出冗余"。

且要满足，性质一：无后效性，即当前的抉择不会对后面的抉择产生影响；

性质二：重复子问题，即把当前问题分解为k个问题。

然后定义状态，

写出状态转移方程，

并从时间和空间的角度优化 状态和状态转移方程。

然后注意处理边界情况。

这题直接定义 dpij表示走到第i层第j个房间时的 最大权值和，

dpij = max(dp[i-1][j-1], dp[i-1][j])

然后处理下左右边界即可。

复杂度 O(n^2)

#include 
#include 

using namespace std;
typedef long long LL;
const int MAXN = 1e2 + 8;

int w[MAXN][MAXN], dp[MAXN][MAXN];

int main()
{
    #ifdef LOCAL
    freopen("2.in", "r", stdin);
    //freopen("2.out", "w", stdout);

    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, i, j, ans = 0;
    cin >> n;
    for(i = 0; i < n; i++){
        for(j = 0; j <= i; j++){ cin >> w[i][j];
        }
    }
    for(i = 0; i < n; i++){
        for(j = 0; j <= i; j++){
            if(i == 0){
                dp[i][j] = w[i][j];
            }
            else if(j == 0){
                dp[i][j] = dp[i-1][j] + w[i][j];
            }
            else if(j == i){
                dp[i][j] = dp[i-1][j-1] + w[i][j];
            }
            else{
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + w[i][j];
            }
        }
    }
    for(j = 0; j < n; j++) ans = max(ans, dp[n-1][j]);
    cout << ans << endl;
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx