一:題目

二:代碼

#include <iostream> #include<vector> using namespace std; int main() {/**思路:1.確定dp數組的定義以及下標的含義dp[i][j] 表示的是一條路徑到達下標i和j時，的最大值 2.確定dp數組的狀態轉移公式我們當前位置的最大值其實是由右上方和左上方中最大的值決定的（題目給出的第一個圖） dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + v[i][j]; 3.確定dp數組的初始化dp數組初始化為0 4.確定dp數組的遍歷順序正常遍歷即可，但是我們需要將我們原始數組中 最上面的一行 和 最左面的一行空出來 因為當 i = 1 j = 1時 我們需要 dp[0][j] 和 dp[i][0] 5.舉例驗證 */ int n;int ans = 0;cin >> n;vector<vector<int> >v1(n+1,vector<int>(n+1,0)); vector<vector<int> >dp(n+1,vector<int>(n+1,0)); for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {cin >> v1[i][j];} }for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) { dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + v1[i][j];if(ans < dp[i][j]) ans = dp[i][j];} }//關于題目中說的 最終左的次數與右的次數相差不能大于1//通過觀察發現 if(n%2 != 0) {cout << dp[n][(n+1)/2];} else {int num1 = dp[n][(n+1)/2];int num2 = dp[n][(n+1)/2+1];cout << max(num1,num2);} //驗證輸出 // for (int i = 0; i <= n; i++) { // for (int j = 0; j <= n; j++) { // cout << v1[i][j] << " "; // } // cout << endl; // } // // cout << "++++++++++++++" << endl; // // for (int i = 0; i <= n; i++) { // for (int j = 0; j <= n; j++) { // cout << dp[i][j] << " "; // } // cout << endl; // }//6 //7 //3 8 //8 1 0 //2 7 4 4 //4 5 2 6 5 //6 7 8 9 10 11return 0; }

這個題是真的狗

總結

以上是生活随笔為你收集整理的蓝桥杯-代码-数字三角形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。