筆試演算法題分享

草船借箭

題目：

題目描述:
程式員小周同學這幾天在看《三國演義》。今天他看到了“草船借箭”這一回，在欽佩諸葛亮巧借東風向曹操“借"箭的同
時，小周想到這麼一個問題: 如果諸葛亮一共派出了N條放置草人的船來“借"箭。“悚慨”的曹操向第1條草船上射了A支
箭、第2條草船上射了B支箭，第3條草船上射的箭的數量等於前面兩條船上箭的數量之和多一支，第4條草船上射的箭的
數量等於前面三條船上的箭的數量之和多一支，...，以此類推，第N條草船上箭的數量等於前面N-1條船上箭的數量之和
多一支。 下麵問題來了，請問這一次諸葛亮一共從曹操那裡“借”了多少支箭呢?
輸入描述
輸入三個正整數N、A和B，三個正整數都不超過1000，並且保證N>1，且兩兩之間用空格隔開。
輸出描述
輸出諸葛亮“借”箭的總數量。結果對1e9+7取模。
樣例輸入
4 1 2
樣例輸出
15

思路：

1. 求出每條船上的箭頭數量。由nums保存

​ a.當天箭頭的數量是前面箭頭數量和+1，由 preSum保存

2. 求出所有總和，即nums數組求和即可

如果寫過斐波拉切數列那麼本題思路就會比較明確。

#include <cmath>
#include <vector>
#include <stdint.h>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <climits>
#include <deque>
#include <bitset>
#include <functional>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <stack>
#include <queue>
using namespace std; 

int main() {
    long long mod = 1e9 + 7;
    int n = -1; cin >> n;
    vector<int> nums(n,0);
    cin >> nums[0] >> nums[1];
    long long preSum = nums[0] + nums[1];
    for (int i = 2; i < n; ++i) {
        nums[i] = (preSum + 1)%mod;
        preSum += nums[i];
        preSum %= mod;
    }
    long long res = 0;
    for (int i = 0; i < nums.size(); ++i) {
        res += nums[i];
        res %= mod;
    }
    cout << res << endl;
    return 0;
}

隨機數選最少數字求和

本題也可見https://blog.csdn.net/qq_43522889/article/details/132460220，但是個人覺得有些鏈接中寫的思路有問題。

題目：

小明用電腦隨機生成了N個正整數，他希望從這N個數中選取若幹個數，使得它們的和等於M。這些隨機生成的數字可能會相同，但是每個數字最多只允許使用一次。
當然這樣的選取方案可能不存在，也可能有多個。
現在希望編寫一個程式，能夠找出數字個數最少的選取方案，輸出對應的最少數字的個數，如果無解輸出“No solution”。
輸入描述：

單組輸入，每組入2行。
第1行包含兩個正整數N和M，分別表示初始輸入的正整數個數和目標數字和（N<=1e3，M<=1e5）。
第2行為N個正整數，兩兩之間用空格隔開（每一個正整數均小於等於1e5）。
輸出描述：

輸出數字個數最少的選取方案中所包含的最少數字個數，如果無解輸出“No solution”。
樣例：

輸入
5 5
1 3 2 1 1
輸出
2

思路：

只需要輸出最後的個數，因此大概率是dp。

dp三要素：

​ dp含義：dp[i][j]表示考慮前i個數字的情況下，組合成j的最少數字個數。

​ 屬性：最小值，最少數字個數。

​ 狀態轉移方程：

dp[i][j] = min({ dp[i][j], dp[i - 1][j] });
if (j >= thisNum) {
dp[i][j] = min({dp[i][j],dp[i - 1][j - thisNum] + 1 });
}

代碼：

#include <cmath>
#include <vector>
#include <stdint.h>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <climits>
#include <deque>
#include <bitset>
#include <functional>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <stack>
#include <queue>
using namespace std; 

int main() {
    int n, m; cin >> n >> m;
    vector<vector<int>> dp(n + 1, vector<int>(m+10, INT_MAX/2));//dp[i][j]表示考慮前i個數字，組合為j的最小的數字個數
    for (int i = 0; i < n + 1; ++i) {
        dp[i][0] = 0;//任何組合組成0 需要的個數是0個
    }
    vector<int> numsVt;
    for (int i = 0; i < n; ++i) {
        int t = -1; cin >> t;
        numsVt.push_back(t);
    }
    for (int i = 1; i <= n; ++i) {
        int thisNum = numsVt[i - 1];
        if (thisNum > m) { continue; }
        dp[i][thisNum] = 1;  //特殊賦值
        
        for (int j = 0; j <= m; ++j) {
            dp[i][j] = min({ dp[i][j], dp[i - 1][j] });
            if (j >= thisNum) {
                dp[i][j] = min({dp[i][j],dp[i - 1][j - thisNum] + 1 });
            }

        }
    }
    if (dp[n][m] == INT_MAX / 2) {
        cout << "No solution" << endl;
    }
    else
    {
        cout << dp[n][m] << endl;
    }
    return 0;
}

我的博客園：https://www.cnblogs.com/swx123
我的github（代碼一般都放在這裡）：https://github.com/578223592