資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在 C++ 中查詢最小和，使得每三個連續元素中至少取一個
假設我們有一個包含 n 個元素的陣列。任務是從陣列中找到元素的最小和，條件是必須從陣列中每三個連續元素中至少選擇一個元素。例如，如果陣列是 [1, 2, 3, 6, 7, 1]，則輸出為 4。如果我們選擇 3 和 1，則 (3 + 1 = 4)。因此，有一些連續元素的子陣列，例如 [1, 2, 3]、[2, 3, 6]、[3, 6, 7]、[6, 7, 1]，我們從每個子陣列中選擇了一個元素。
假設 sum(i) 返回最小可能的和，其中 arr[i] 是解決方案的一部分且是最後選擇的元素。那麼我們的結果是 sum(i – 1)、sum(i – 2)、sum(i – 3) 的最小值。我們可以看到這存在重疊子問題，因此我們可以使用動態規劃方法來解決這個問題。
示例
#include <iostream>
using namespace std;
int minOfThree(int a, int b, int c) {
return min(min(a, b), c);
}
int getMinSum(int arr[], int n) {
int sum[n];
sum[0] = arr[0];
sum[1] = arr[1];
sum[2] = arr[2];
for (int i=3; i<n; i++)
sum[i] = arr[i] + minOfThree(sum[i-3], sum[i-2], sum[i-1]);
return minOfThree(sum[n-1], sum[n-2], sum[n-3]);
}
int main() {
int arr[] = {1, 2, 3, 20, 2, 10, 1};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Minimum sum is: " << getMinSum(arr, n);
}輸出
Minimum sum is: 4
更新於：2019-12-18
296 次瀏覽
廣告