数字三角形（向左下走的次数与向右下走的次数相差不能超过 1）

December 19, 2022

892 views

1109 words

**二维数组初始化`fill(arr[0], arr[0] + n * n, 0)`**

### DFS 超时

```c++
#include<bits/stdc++.h>
using namespace std;
int num[101][101] = {0};
int add[101][101] = {0};
int n;
vector<int> ans;

void dfs(int l, int r, int x, int y){
  if(l > n/2 || r > n/2){
    return;
  }
    if(x == n - 1){
        if(abs(l - r) > 1){
            return;
        }
        ans.push_back(add[x][y]);
        return;
    }
  
    l++;
    add[x + 1][y] = num[x + 1][y] + add[x][y];
    s(l, r, x + 1, y);
    add[x + 1][y] = num[x + 1][y];
    l--;

r++;
    add[x + 1][y + 1] = num[x + 1][y + 1] + add[x][y];
    s(l, r, x + 1, y + 1);
    add[x + 1][y + 1] = num[x + 1][y + 1];
    r--;
}

int main()
{
    cin >> n;
  
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            scanf("%d", &num[i][j]);
        }
    }
    add[0][0] = num[0][0];
    dfs(0, 0, 0, 0);
    auto max = max_element(ans.begin(), ans.end());
    cout << *max;
  
    return 0;
}
```

### 动态规划

```c++
#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin >> n;
	int num[n][n], dp[n][n];
	fill(num[0], num[0] + n * n, 0);
	fill(dp[0], dp[0] + n * n, 0);
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= i; j++){
			scanf("%d", &num[i][j]);
		}
	}
	dp[0][0] = num[0][0];
	for(int i = 0; i < n; i++){
		for(int j = 0; j <= i; j++){
			if(i - 1 >= 0 && j - 1 < 0){
				dp[i][j] = dp[i - 1][j] + num[i][j];
			}else if(i - 1 >= 0 && j - 1 >= 0){
				dp[i][j] = max(dp[i - 1][j - 1] + num[i][j], dp[i - 1][j] + num[i][j]);
			}
		}
	}
// 因为向左下走的次数与向右下走的次数相差不能超过 1
// 所以答案一定在中间
	if(n%2 == 0){
		cout << max(dp[n - 1][n / 2 - 1], dp[n - 1][n / 2]);
	}else{
		cout << dp[n - 1][n / 2];
	}

return 0;
}
```

Last modification：December 19, 2022