# 矩阵取数游戏

## 题目

### 输入样例:

``````3
1 3 3
2 1 3
2 2 1
``````

### 输出样例:

``11``

## 题解

### 分治算法

``````#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> vec(501, vector<int>(501));
vector<vector<int>> dp(501, vector<int>(501, -1));
int ans = 0, N;
int work(int i, int j) {
if (dp[i][j] != -1) {//记忆化数组
return dp[i][j];
}
if(i==N||j==N){ //边界条件
dp[i][j]=0;
return 0;
}
dp[i][j]=max(work(i + 1, j), work(i, j + 1))+vec[i][j];//下面或者右面
return dp[i][j];
}
int main() {
int n;
cin >> n;
N = n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> vec[i][j];
}
}
cout<<work(0,0);
system("pause");
}``````

### 动态规划

``````

/*
动态规划
1.dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j]
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){

int n;
cin>>n;
vector<vector<int>> a(n+1,vector<int>(n+1)),dp(n+1,vector<int>(n+1,0));
for(int i=1;i<n+1;i++){
for(int j=1;j<n+1;j++){
scanf("%d",&a[i][j]);
}
}

for(int i=1;i<n+1;i++){
for(int j=1;j<n+1;j++){
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];
}
}
cout<<dp[n][n];
system("pause");
}``````