---
tags: 文華社課
---
> 文華高中電腦研究社29th
> 編輯 : 黃昱凱、陳睿哲

# C++從零入門Level 3-2

---

## 動態規劃 DP (dynamic programming)
### 引言

我們在上一節課有提到說，有些情況下使用貪心演算法的答案不一定是正確的
面對這種題目時，**依照題目**，可以使用的方法有很多
像cdq分治、二分搜尋法、DFS、BFS、線段樹、BIT...等等等等
這些技巧幾乎都可以幫助我們達到**減少執行時間**的目的
一個常用且非常有效的方法，就是DP

### Dynamic Programming
Dynamic、在以前是抄筆記的意思
Programming、編程

DP的核心觀念在**如果有重複計算同樣結果的行為，就抄在筆記上，遇到直接拿出來用**
長話短說就是**一樣的事情不做第二遍**
把**問題分割成多個小問題、逐個擊破再重新組合答案**
是不是很有分治法的味道阿w

沒錯!其實DP就是只是有記憶的分治法
下面請看範例:

---

#### 費波納契數列
一數列，第一項和第二項為1，排成一列，**且該數字為前兩項數字的和**

1、 1、 2、 3、 5、 8、 13、 21、 34、 55、 89

**fib(n) = {fib(n-1)+fib(n-2),n >= 1,fib(1) = fib(2) = 1}**

> 沒有DP
> 時間複雜度O(2^n^)

int fib(int n){
    if (n == 1 or n == 2)
        return 1;
    return fib(n-1)+fib(n-2);
}

> DP
> 時間複雜度O(n)

int dp[1000] = {0};

int fib(int n){
    if (n == 1 or n == 2)
        return 1;
    if (dp[n] != 0) return dp[n];
    dp[n] = fib(n-1)+fib(n-2);
    return dp[n];
}

---

#### 實作範例 0-1背包問題

> 看螢幕

#include <iostream>
#include <string.h>

using namespace std;

int num;
int v[1005];
int k[1005];
int dp[1005][105];
int solve(int idx,int remain){

    if (idx == num or remain == 0){
        return 0;
    }

    else if (dp[idx][remain] != -1){
        return dp[idx][remain];
    }

    else if (remain < v[idx]){
        dp[idx][remain] = solve(idx+1,remain);
        return dp[idx][remain];
    }

    int take = solve(idx+1,remain-v[idx])+k[idx];
    int dont = solve(idx+1,remain);
    dp[idx][remain] = max(take,dont);

    return dp[idx][remain];
}

int main(){
    while (cin >> num){
        memset(dp,-1,sizeof(dp));
        for (int i = 0;i < num;i++){
            cin >> v[i] >> k[i];
        }
        int ans = solve(0,100);
        cout << ans << endl;
    }
}

---

#### 實作範例二 不能貪心的換錢問題

你們會好奇上堂課講到的換錢問題嗎~?
其實不難，就像上面講的，開一個筆記儲存結果即可

**題目:**

蘿莉國有面額各為1000、500、100、50、10、**7**、5、1的鈔票
現在有一個人拿了n元，且n的範圍如右: 0<n<10000
請輸出**有多少種可能為組合的鈔票呢~?**

一題兩用真爽(X

#include<bits/stdc++.h>
using namespace std;
long long int money[10000] = {0};
int arr[8] = {1, 5, 7, 10, 50, 100, 500, 1000};
int main(){
  money[0] = 1;
  for(int i = 0; i < 8; i++){
    for(int j = arr[i]; j <= 10000; j++){
      money[j] += money[j - arr[i]];
    }
  }
  int n;
  while(cin >> n){
    cout << money[n] << endl;
  }
  return 0;
}

範例輸入1:

8

範例輸出1:

3

輸出講解，有:、1元\*8、1元\*3 + 5元\*1 和 1元\*1 + 7元\*1這三種組合

範例輸入2:

8941

範例輸出2:

1892655596636

:::danger

- [ ] [d052: 11456 - Trainsorting](https://zerojudge.tw/ShowProblem?problemid=d052)
Tip: LIS + LDS dp

:::
:::danger
- [ ] [c147: 105北二5搬家規劃問題](https://zerojudge.tw/ShowProblem?problemid=c147)
DP，對所有可能價格找最佳解
:::

---
> 目錄: https://hackmd.io/@lolicon5208/HkSNa1kIY

## 參考答案
### d052

#include<bits/stdc++.h>
using namespace std;
#define N 2005
int a[N] = {0};
int lis[N];
int lds[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int k;
    cin >>k;
    while(k --)
    {
        int n;
        cin >> n;
        int ans = 0;
        if (n == 0) {
                cout << 0 <<endl;
            continue;
        }
        for(int i = 0;i < n;i ++) cin >> a[i];
        for(int i = n - 1; i >= 0; i --)
        {
            lis[i] = 1;
            lds[i] = 1;
            for(int j = n - 1; j > i; j --)
            {
                if (a[i] > a[j]) lis[i] = max(lis[i], lis[j] + 1);
                if (a[i] < a[j]) lds[i] = max(lds[i], lds[j] + 1);
            }
            ans = max(ans, lis[i] + lds[i] - 1);
        }
        cout << ans <<endl;
    }
}

### c147

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 1005
#define MAX 1000005
int w[N], v[N], cnt = 0;
LL max_w;
int a[MAX] = {0};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s1, s2;
    stringstream ss, sss;
    getline(cin, s1);
    ss << s1;
    while(ss >> s1){
        w[cnt ++] = stoi(s1);
    }
    getline(cin, s2);
    sss << s2;
    cnt = 0;
    while(sss >> s2){
        v[cnt ++] = stoi(s2);
    }
    cin >> max_w;
    for(int i = 0;i < cnt;i ++){
        for(int j = max_w;j > 0;j --){
            if (j - w[i] >= 0) a[j] = max(a[j], a[j-w[i]] + v[i]);
        }
    }
    cout << a[max_w]<<endl;
    return 0;
}