資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：透過刪除數字找到最大加法得分
假設我們有一個名為nums的數字列表。我們考慮一個操作，我們可以選擇一個數字，然後將其移除，並將我們的分數增加所選數字及其兩個相鄰數字之和。只要我們不選擇列表中的第一個或最後一個數字，我們就可以執行此操作任意多次。我們必須找到可能的最大分數。
因此，如果輸入類似於nums = [2, 3, 4, 5, 6]，則輸出將為39，因為我們可以選擇5，則總和為(4 + 5 + 6) = 15，陣列將為[2, 3, 4, 6]，然後選擇4，所以總和是(3 + 4 + 6) = 13，陣列將為[2, 3, 6]，選擇3，總和將為(2 + 3 + 6) = 11，所以總和為15 + 13 + 11 = 39
為了解決這個問題，我們將遵循以下步驟：
- n := nums的大小
- 如果 n < 3，則
- 定義一個大小為(n + 1) x (n + 1) 的二維陣列
- 用於初始化len := 3，當len <= n時，更新（len加1），執行：
- 用於初始化i := 1，當i + len - 1 <= n時，更新（i加1），執行：
- r := i + len - 1
- ans := 0
- 用於初始化k := i + 1，當k <= r - 1時，更新（k加1），執行：
- curr := dp[i, k] + dp[k, r] + nums[k - 1]
- 如果curr > ans，則
- ans := ans + nums[i - 1] + nums[r - 1]
- dp[i, r] := ans
- 用於初始化i := 1，當i + len - 1 <= n時，更新（i加1），執行：
- 返回dp[1, n]
讓我們看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<int>& nums) {
int n = nums.size();
if (n < 3) return 0;
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
for (int len = 3;
len <= n; ++len) {
for (int i = 1; i + len - 1 <= n; ++i) {
int r = i + len - 1;
int ans = 0;
for (int k = i + 1; k <= r - 1; ++k) {
int curr = dp[i][k] + dp[k][r] + nums[k - 1];
if (curr > ans)
ans = curr;
}
ans += nums[i - 1] + nums[r - 1]; dp[i][r] = ans;
}
}
return dp[1][n];
}
};
int solve(vector<int>& nums) {
return (new Solution())->solve(nums);
}
main(){
vector<int> v = {2, 3, 4, 5, 6};
cout << solve(v);
}輸入
[2, 3, 4, 5, 6]
輸出
39
更新於：2020年11月20日
127 次瀏覽
廣告