动态规划 数字三角形

P1216 [IOI 1994] 数字三角形 Number Triangles - 洛谷

第一次有TLE。

#includeusing namespace std;int r;int dp(int c,int w,vector&a){if(c==r)return a[(c-1)*c/2+w-1];return a[(c-1)*c/2+w-1]+max(dp(c+1,w,a),dp(c+1,w+1,a));}signed main(){cin>>r;vectora(r*(r+1)/2);for(int i=0;i>a[i];cout<<dp(1,1,a);return 0;}

这段代码使用递归的方式计算了一个数字三角形（类似于杨辉三角的结构）从顶部到底部的最大路径和。虽然逻辑上是正确的，但它的时间复杂度非常高，导致在大输入时超时。

原因分析：
1. 递归的指数时间复杂度：当前的 dp 函数是一个纯递归实现，没有记忆化（Memoization），导致大量重复计算。比如，dp(c, w) 会被多次调用，每次都会重新计算，即使之前已经计算过相同参数的结果。
   - 对于 r 层的三角形，递归调用的次数是 `O(2^r)`，因为每个点会分裂成两个子问题（左下和右下）。
   - 当 `r` 较大时（比如 `r = 100`），`2^100` 是一个天文数字，必然超时。

2. 输入规模：题目中 r 的范围可能很大（比如 `r = 100` 或更大），而递归解法无法处理这样的规模。

方法 1：记忆化搜索
在递归的基础上，用一个二维数组 `memo` 缓存已经计算过的 `dp(c, w)` 的结果，避免重复计算。通过缓存子问题的结果，将时间复杂度从指数级 (`O(2^r)`) 降低到多项式级 (`O(r^2)`)。

#includeusing namespace std;int r;vector<vector> memo; // 记忆化表int dp(int c, int w, vector& a) {if (c == r) return a[(c-1)*c/2 + w-1];if (memo[c][w] != -1) return memo[c][w]; // 如果已经计算过，直接返回memo[c][w] = a[(c-1)*c/2 + w-1] + max(dp(c+1, w, a), dp(c+1, w+1, a)); // 缓存结果return memo[c][w];}signed main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> r;memo.assign(r + 1, vector(r + 1, -1)); // 初始化记忆化表vector a(r * (r + 1) / 2);for (int i = 0; i > a[i];cout << dp(1, 1, a);return 0;}

方法 2：从底向上的动态规划
从三角形的底部开始，逐层向上计算每个点到最底层的最大路径和，最终 `dp[1][1]` 就是答案。直接按层计算，避免了递归的开销，更高效。

#includeusing namespace std;int r;signed main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin>>r;vectora(r*(r+1)/2);for(int i=0;i>a[i];vector<vector>dp(r+1,vector(r+1,0));for(int i=r;i>=1;i--){for(int j=1;j<=i;j++){if(i==r)dp[i][j]=a[i*(i-1)/2+j-1];else dp[i][j]=a[i*(i-1)/2+j-1]+max(dp[i+1][j],dp[i+1][j+1]);}}cout<<dp[1][1];return 0;}

艺术品交易