测试了三种优化级别的素数判断方案。




```cpp
#include <iostream>
#include <algorithm>
#include <cmath>
#include <catch2/catch.hpp>

bool is_prime_0(int n) {
    for(int i = 2; i < n; ++i) {
        if (n % i == 0)
            return false;
    }
    return true;
}

bool is_prime_1(int n) {
    if (n % 2 == 0)
        return n == 2;
    int sq = floor(sqrt(n));
    for (int i = sq | 1; i > 1; i -= 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

bool is_prime_2(int n) {
    if (n == 2 || n == 3)
        return true;
    if (n % 6 != 1 || n % 6 != 5)
        return false;
    int sq = floor(sqrt(n));
    for(int i = 5;i <= sq; i += 6) {       
        if(n % i == 0 || n % (i+2) == 0)  
            return false;
    }
    return true;
}

TEST_CASE("Is Prime") {
    int num = 9989899;

    BENCHMARK("is_prime_0") {
        return is_prime_0(num);
    };

    BENCHMARK("is_prime_1") {
        return is_prime_1(num);
    };

    BENCHMARK("is_prime_2") {
        return is_prime_2(num);
    };
}
```

Benchmark 结果
```
benchmark name                       samples       iterations    estimated
                                     mean          low mean      high mean
                                     std dev       low std dev   high std dev
-------------------------------------------------------------------------------
is_prime_0                                     100             1     3.11125 s 
                                        32.4578 ms    31.9605 ms    33.1967 ms 
                                        3.04949 ms      2.275 ms    4.22213 ms 
                                                                               
is_prime_1                                     100             7      3.374 ms 
                                        4.72644 us    4.63879 us    5.03562 us 
                                        735.203 ns    234.881 ns    1.64281 us 
                                                                               
is_prime_2                                     100         31531     3.1531 ms 
                                        1.27671 ns    1.15347 ns    1.70551 ns 
                                        1.04434 ns   0.334288 ns    2.36015 ns 
```

素数判断的优化

> 洛谷 [P1217](https://www.luogu.com.cn/problem/P1217)

# [USACO1.5] 回文质数 Prime Palindromes

## 题目描述

因为 $151$ 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 $151$ 是回文质数。

写一个程序来找出范围 $[a,b] (5 \le a < b \le 100,000,000)$（一亿）间的所有回文质数。



## 输入格式

第一行输入两个正整数 $a$ 和 $b$。

## 输出格式

输出一个回文质数的列表，一行一个。

## 样例 #1

### 样例输入 #1

```
5 500
```

### 样例输出 #1

```
5
7
11
101
131
151
181
191
313
353
373
383
```

## 提示

Hint 1: Generate the palindromes and see if they are prime.

提示 1: 找出所有的回文数再判断它们是不是质数（素数）.


Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.

提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。


题目翻译来自NOCOW。

USACO Training Section 1.5


产生长度为 $5$ 的回文数：

```cpp
for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
     for (d2 = 0; d2 <= 9; d2++) {
         for (d3 = 0; d3 <= 9; d3++) {
           palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
         }
     }
 }

```

# 个人题解

## 分析

看这个数字范围，如果直接遍历然后判断素数和回文数会很慢，可以考虑构造回文数然后提素数。

1. 显然，1位数和2位数的回文质数就3个，5,7,11
2. 显然，所有的偶数位的回文数不是质数

## 代码

因此，对这个过程加以优化，可以简单写出以下代码

```cpp
#include <iostream>
#include <algorithm>
#include <cmath>

bool is_prime_ge5(int n) {
    int sq = floor(sqrt(n));
    for (int num = sq | 1; num > 1; num -= 2) {
        if (n % num == 0) {
            return false;
        }
    }
    return true;
}

int main() {
#ifdef OHTOAI_LOCAL_MACHINE
    std::freopen("input.txtendlr", stdin);
    std::freopen("output.txtendlw", stdout);
#endif
    using std::cin;
    using std::cout;
    using std::endl;
    std::ios::sync_with_stdio(false);

    int a, b;
    int palindrome_withen_100[] = { 5, 7, 11 };

    cin >> a >> b;
    for (auto n : palindrome_withen_100) {
        if (a <= n && n <= b)
            cout << n << endl;
    }

    for (int dt1 = 1; dt1 <= 9; dt1 += 2) {
        int num1 = dt1 * 101;
        if (num1 + 101 < a)
            continue;
        for (int dt2 = 0; dt2 <= 9; dt2++) {
            int num = num1 + dt2 * 10;
            if (num + 10 < a)
                continue;
            else if (b < num)
                break;
            else if (is_prime_ge5(num))
                cout << num << endl;
        }
    }

    for (int dt1 = 1; dt1 <= 9; dt1 += 2) {
        int num1 = dt1 * 10001;
        if (num1 + 10001 < a)
            continue;
        for (int dt2 = 0; dt2 <= 9; dt2++) {
            int num2 = num1 + dt2 * 1010;
            if (num2 + 1010 < a)
                continue;
            for (int dt3 = 0; dt3 <= 9; dt3++) {
                int num = num2 + dt3 * 100;
                if (num + 100 < a)
                    continue;
                else if (b < num)
                    break;
                else if (is_prime_ge5(num)) {
                    cout << num << endl;
                }
            }
        }
    }

    
    for (int dt1 = 1; dt1 <= 9; dt1 += 2) {
        int num1 = dt1 * 1000001;
        if (num1 + 1000001 < a)
            continue;
        for (int dt2 = 0; dt2 <= 9; dt2++) {
            int num2 = num1 + dt2 * 100010;
            if (num2 + 100010 < a)
                continue;
            for (int dt3 = 0; dt3 <= 9; dt3++) {
                int num3 = num2 + dt3 * 10100;
                if (num3 + 10100 < a)
                    continue;
                for (int dt4 = 0; dt4 <= 9; dt4++) {
                    int num = num3 + dt4 * 1000;
                    if (num + 1000 < a)
                        continue;
                    else if (b < num)
                        break;
                    else if (is_prime_ge5(num)) {
                        cout << num << endl;
                    }
                }
            }
        }
    }

    return 0;
}
```

## 终极优化

容易得到1亿范围内的所有回文质数，因此很容易写出以下的代码

```cpp
#include <algorithm>
#include <cstdio>

int main() {
    constexpr int list[] = {
        5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181, 18481, 19391, 19891, 19991, 30103, 30203, 30403, 30703, 30803, 31013, 31513, 32323, 32423, 33533, 34543, 34843, 35053, 35153, 35353, 35753, 36263, 36563, 37273, 37573, 38083, 38183, 38783, 39293, 70207, 70507, 70607, 71317, 71917, 72227, 72727, 73037, 73237, 73637, 74047, 74747, 75557, 76367, 76667, 77377, 77477, 77977, 78487, 78787, 78887, 79397, 79697, 79997, 90709, 91019, 93139, 93239, 93739, 94049, 94349, 94649, 94849, 94949, 95959, 96269, 96469, 96769, 97379, 97579, 97879, 98389, 98689, 1003001, 1008001, 1022201, 1028201, 1035301, 1043401, 1055501, 1062601, 1065601, 1074701, 1082801, 1085801, 1092901, 1093901, 1114111, 1117111, 1120211, 1123211, 1126211, 1129211, 1134311, 1145411, 1150511, 1153511, 1160611, 1163611, 1175711, 1177711, 1178711, 1180811, 1183811, 1186811, 1190911, 1193911, 1196911, 1201021, 1208021, 1212121, 1215121, 1218121, 1221221, 1235321, 1242421, 1243421, 1245421, 1250521, 1253521, 1257521, 1262621, 1268621, 1273721, 1276721, 1278721, 1280821, 1281821, 1286821, 1287821, 1300031, 1303031, 1311131, 1317131, 1327231, 1328231, 1333331, 1335331, 1338331, 1343431, 1360631, 1362631, 1363631, 1371731, 1374731, 1390931, 1407041, 1409041, 1411141, 1412141, 1422241, 1437341, 1444441, 1447441, 1452541, 1456541, 1461641, 1463641, 1464641, 1469641, 1486841, 1489841, 1490941, 1496941, 1508051, 1513151, 1520251, 1532351, 1535351, 1542451, 1548451, 1550551, 1551551, 1556551, 1557551, 1565651, 1572751, 1579751, 1580851, 1583851, 1589851, 1594951, 1597951, 1598951, 1600061, 1609061, 1611161, 1616161, 1628261, 1630361, 1633361, 1640461, 1643461, 1646461, 1654561, 1657561, 1658561, 1660661, 1670761, 1684861, 1685861, 1688861, 1695961, 1703071, 1707071, 1712171, 1714171, 1730371, 1734371, 1737371, 1748471, 1755571, 1761671, 1764671, 1777771, 1793971, 1802081, 1805081, 1820281, 1823281, 1824281, 1826281, 1829281, 1831381, 1832381, 1842481, 1851581, 1853581, 1856581, 1865681, 1876781, 1878781, 1879781, 1880881, 1881881, 1883881, 1884881, 1895981, 1903091, 1908091, 1909091, 1917191, 1924291, 1930391, 1936391, 1941491, 1951591, 1952591, 1957591, 1958591, 1963691, 1968691, 1969691, 1970791, 1976791, 1981891, 1982891, 1984891, 1987891, 1988891, 1993991, 1995991, 1998991, 3001003, 3002003, 3007003, 3016103, 3026203, 3064603, 3065603, 3072703, 3073703, 3075703, 3083803, 3089803, 3091903, 3095903, 3103013, 3106013, 3127213, 3135313, 3140413, 3155513, 3158513, 3160613, 3166613, 3181813, 3187813, 3193913, 3196913, 3198913, 3211123, 3212123, 3218123, 3222223, 3223223, 3228223, 3233323, 3236323, 3241423, 3245423, 3252523, 3256523, 3258523, 3260623, 3267623, 3272723, 3283823, 3285823, 3286823, 3288823, 3291923, 3293923, 3304033, 3305033, 3307033, 3310133, 3315133, 3319133, 3321233, 3329233, 3331333, 3337333, 3343433, 3353533, 3362633, 3364633, 3365633, 3368633, 3380833, 3391933, 3392933, 3400043, 3411143, 3417143, 3424243, 3425243, 3427243, 3439343, 3441443, 3443443, 3444443, 3447443, 3449443, 3452543, 3460643, 3466643, 3470743, 3479743, 3485843, 3487843, 3503053, 3515153, 3517153, 3528253, 3541453, 3553553, 3558553, 3563653, 3569653, 3586853, 3589853, 3590953, 3591953, 3594953, 3601063, 3607063, 3618163, 3621263, 3627263, 3635363, 3643463, 3646463, 3670763, 3673763, 3680863, 3689863, 3698963, 3708073, 3709073, 3716173, 3717173, 3721273, 3722273, 3728273, 3732373, 3743473, 3746473, 3762673, 3763673, 3765673, 3768673, 3769673, 3773773, 3774773, 3781873, 3784873, 3792973, 3793973, 3799973, 3804083, 3806083, 3812183, 3814183, 3826283, 3829283, 3836383, 3842483, 3853583, 3858583, 3863683, 3864683, 3867683, 3869683, 3871783, 3878783, 3893983, 3899983, 3913193, 3916193, 3918193, 3924293, 3927293, 3931393, 3938393, 3942493, 3946493, 3948493, 3964693, 3970793, 3983893, 3991993, 3994993, 3997993, 3998993, 7014107, 7035307, 7036307, 7041407, 7046407, 7057507, 7065607, 7069607, 7073707, 7079707, 7082807, 7084807, 7087807, 7093907, 7096907, 7100017, 7114117, 7115117, 7118117, 7129217, 7134317, 7136317, 7141417, 7145417, 7155517, 7156517, 7158517, 7159517, 7177717, 7190917, 7194917, 7215127, 7226227, 7246427, 7249427, 7250527, 7256527, 7257527, 7261627, 7267627, 7276727, 7278727, 7291927, 7300037, 7302037, 7310137, 7314137, 7324237, 7327237, 7347437, 7352537, 7354537, 7362637, 7365637, 7381837, 7388837, 7392937, 7401047, 7403047, 7409047, 7415147, 7434347, 7436347, 7439347, 7452547, 7461647, 7466647, 7472747, 7475747, 7485847, 7486847, 7489847, 7493947, 7507057, 7508057, 7518157, 7519157, 7521257, 7527257, 7540457, 7562657, 7564657, 7576757, 7586857, 7592957, 7594957, 7600067, 7611167, 7619167, 7622267, 7630367, 7632367, 7644467, 7654567, 7662667, 7665667, 7666667, 7668667, 7669667, 7674767, 7681867, 7690967, 7693967, 7696967, 7715177, 7718177, 7722277, 7729277, 7733377, 7742477, 7747477, 7750577, 7758577, 7764677, 7772777, 7774777, 7778777, 7782877, 7783877, 7791977, 7794977, 7807087, 7819187, 7820287, 7821287, 7831387, 7832387, 7838387, 7843487, 7850587, 7856587, 7865687, 7867687, 7868687, 7873787, 7884887, 7891987, 7897987, 7913197, 7916197, 7930397, 7933397, 7935397, 7938397, 7941497, 7943497, 7949497, 7957597, 7958597, 7960697, 7977797, 7984897, 7985897, 7987897, 7996997, 9002009, 9015109, 9024209, 9037309, 9042409, 9043409, 9045409, 9046409, 9049409, 9067609, 9073709, 9076709, 9078709, 9091909, 9095909, 9103019, 9109019, 9110119, 9127219, 9128219, 9136319, 9149419, 9169619, 9173719, 9174719, 9179719, 9185819, 9196919, 9199919, 9200029, 9209029, 9212129, 9217129, 9222229, 9223229, 9230329, 9231329, 9255529, 9269629, 9271729, 9277729, 9280829, 9286829, 9289829, 9318139, 9320239, 9324239, 9329239, 9332339, 9338339, 9351539, 9357539, 9375739, 9384839, 9397939, 9400049, 9414149, 9419149, 9433349, 9439349, 9440449, 9446449, 9451549, 9470749, 9477749, 9492949, 9493949, 9495949, 9504059, 9514159, 9526259, 9529259, 9547459, 9556559, 9558559, 9561659, 9577759, 9583859, 9585859, 9586859, 9601069, 9602069, 9604069, 9610169, 9620269, 9624269, 9626269, 9632369, 9634369, 9645469, 9650569, 9657569, 9670769, 9686869, 9700079, 9709079, 9711179, 9714179, 9724279, 9727279, 9732379, 9733379, 9743479, 9749479, 9752579, 9754579, 9758579, 9762679, 9770779, 9776779, 9779779, 9781879, 9782879, 9787879, 9788879, 9795979, 9801089, 9807089, 9809089, 9817189, 9818189, 9820289, 9822289, 9836389, 9837389, 9845489, 9852589, 9871789, 9888889, 9889889, 9896989, 9902099, 9907099, 9908099, 9916199, 9918199, 9919199, 9921299, 9923299, 9926299, 9927299, 9931399, 9932399, 9935399, 9938399, 9957599, 9965699, 9978799, 9980899, 9981899, 9989899, 
    };
    constexpr auto Length = sizeof(list) / sizeof(list[0]);

    int a, b;
    scanf("%d %d", &a, &b);
    auto low = std::lower_bound(list, list + Length, a);
    auto high = std::upper_bound(low, list + Length, b);
    for (auto e = low; e != high; ++e) {
        printf("%d\n", *e);
    }
    return 0;
}
```

回文质数

# 一个简单的动态规划题目

## 题目描述

假设您是个土豪，身上带了足够的 $1$ 元以及 $n$ 种奇葩面值的钞票。现在您的目标是凑出某个金额$w$，需要用到尽量少的钞票。



## 输入格式

程序的输入共有两行：  
第一行为 $2$ 个整数 $n$ 和 $w$  
第二行为 $n$ 个整数 $p_i$ 代表除了 $1$ 元以外的其他钞票面额

## 输出格式

一个整数，凑出目标金额使用的最少的钞票数量

## 样例 #1

### 样例输入 #1

```
2 15
5 11
```

### 样例输出 #1

```
3
```

## 样例 #2

### 样例输入 #2

```
4 99
5 7 20 50
```

### 样例输出 #2

```
6
```

# 说明

$1 \leq n\leq 100$  
$0 \leq w\leq 10^6$

# 示例题解

```cpp
#include <iostream>
#include <algorithm>

int main() {
#ifdef OHTOAI_LOCAL_MACHINE
    std::freopen("input.txt", "r", stdin);
#endif
    using std::cin;
    using std::cout;
    using std::endl;
    std::ios::sync_with_stdio(false);

    int f[1000001] = {0};
    int money[100];

    int n, w;
    cin >> n >> w;
    for (int i = 0; i < n; ++i) {
        cin >> money[i];
    }

    std::sort(money, money + n);
    for (int i = 0; i < n; ++i) {
        cout << money[i] << ", ";
    }
    cout << endl;

    for (int i = 2; i <= w; ++i) {
        int min_cost = f[i - 1] + 1;
        for (int c = 0; c < n && i >= money[c]; ++c) {
            auto new_cost = f[i - money[c]] + 1;
            if(min_cost > new_cost) {
                min_cost = new_cost;
            }
        }
        f[i] = min_cost;
    }
    cout << f[w] << endl;

    return 0;
}
```

一个简单的动态规划题目

# 什么是动态规划（Dynamic Programming）？动态规划的意义是什么？

 **Author:** [阮行止]

 **Link:** [https://www.zhihu.com/question/23995189/answer/613096905]

## 0. intro  
　　很有意思的问题。以往见过许多教材，对动态规划（DP）的引入属于“奉天承运，皇帝诏曰”式：不给出一点引入，见面即拿出一大堆公式吓人；学生则死啃书本，然后突然顿悟。针对入门者的教材不应该是这样的。恰好我给入门者讲过四次DP入门，迭代出了一套比较靠谱的教学方法，所以今天跑过来献丑。

　　现在，我们试着自己来一步步“重新发明”DP。



## 1. 从一个生活问题谈起  
　　先来看看生活中经常遇到的事吧——假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，**需要用到尽量少的钞票。**

　　依据生活经验，我们显然可以采取这样的策略：能用100的就尽量用100的，否则尽量用50的……依次类推。在这种策略下，666=6×100+1×50+1×10+1×5+1×1，共使用了10张钞票。

　　这种策略称为“**贪心**”：假设我们面对的局面是“需要凑出w”，**贪心策略会尽快让w变得更小**。能让w少100就尽量让它少100，这样我们接下来面对的局面就是凑出w-100。长期的生活经验表明，贪心策略是正确的。

　　但是，如果我们换一组钞票的面值，贪心策略就也许不成立了。如果一个奇葩国家的钞票面额分别是1、5、11，那么我们在凑出15的时候，贪心策略会出错：  
　　15=1×11+4×1 （贪心策略使用了5张钞票）  
　　15=3×5 （正确的策略，只用3张钞票）  
　　为什么会这样呢？贪心策略错在了哪里？

**鼠目寸光。**  
　　刚刚已经说过，贪心策略的纲领是：“尽量使接下来面对的w更小”。这样，贪心策略在w=15的局面时，会优先使用11来把w降到4；但是在这个问题中，凑出4的代价是很高的，必须使用4×1。如果使用了5，w会降为10，虽然没有4那么小，但是凑出10只需要两张5元。  
　　在这里我们发现，贪心是一种**只考虑眼前情况**的策略。

　　那么，现在我们怎样才能避免鼠目寸光呢？

　　如果直接暴力枚举凑出w的方案，明显复杂度过高。太多种方法可以凑出w了，枚举它们的时间是不可承受的。我们现在来尝试找一下性质。

  


　　重新分析刚刚的例子。w=15时，我们如果取11，接下来就面对w=4的情况；如果取5，则接下来面对w=10的情况。我们发现这些问题都有相同的形式：“给定w，凑出w所用的最少钞票是多少张？”接下来，我们用f(n)来表示“凑出n所需的最少钞票数量”。

　　那么，如果我们取了11，最后的代价（用掉的钞票总数）是多少呢？  
　　明显$\text{cost} = f(4) + 1 = 4 + 1 = 5$ ，它的意义是：利用11来凑出15，付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。  
　　依次类推，马上可以知道：如果我们用5来凑出15，cost就是$f(10) + 1 = 2 + 1 = 3$ 。

　　那么，现在w=15的时候，我们该取那种钞票呢？**当然是各种方案中，cost值最低的那一个**！

　　- 取11：$\text{cost}=f(4)+1=4+1=5$  
　　- 取5： $\text{cost}=f(10)+1=2+1=3$  
　　- 取1： $\text{cost}=f(14)+1=4+1=5$

　　显而易见，cost值最低的是取5的方案。**我们通过上面三个式子，做出了正确的决策**！

　　这给了我们一个**至关重要**的启示—— $f(n)$ 只与 $f(n-1),f(n-5),f(n-11)$ 相关；更确切地说：

$f(n)=\min\{f(n-1),f(n-5),f(n-11)\}+1$

　　这个式子是非常激动人心的。我们要求出f(n)，只需要求出几个更小的f值；既然如此，我们从小到大把所有的f(i)求出来不就好了？注意一下边界情况即可。代码如下：

![]((20190303)什么是动态规划Dynamic_Programming动态规划的意义是什么_阮行止/v2-6a5ba74fb90968533ece429ed329c903_r.jpg)  
　　我们以 $O(n)$ 的复杂度解决了这个问题。现在回过头来，我们看看它的原理：

　　- $f(n)$ 只与$f(n-1),f(n-5),f(n-11)$的**值**相关。  
　　- 我们只关心 $f(w)$ 的**值**，不关心是怎么凑出w的。

　　这两个事实，保证了我们做法的正确性。它比起贪心策略，会分别算出取1、5、11的代价，从而做出一个正确决策，这样就避免掉了“鼠目寸光”！

　　它与暴力的区别在哪里？我们的暴力枚举了“使用的硬币”，然而这属于冗余信息。我们要的是答案，根本不关心这个答案是怎么凑出来的。譬如，要求出f(15)，只需要知道f(14),f(10),f(4)的值。**其他信息并不需要。**我们舍弃了冗余信息。我们只记录了对解决问题有帮助的信息——f(n).

　　我们能这样干，取决于问题的性质：求出f(n)，只需要知道几个更小的f(c)。**我们将求解f(c)称作求解f(n)的“子问题”。**

  


**这就是DP**（动态规划，dynamic programming）.

**将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解**。


> 思考题：请稍微修改代码，输出我们凑出w的**方案**。

## 2. 几个简单的概念  
【无后效性】

　　一旦f(n)确定，“我们如何凑出f(n)”就再也用不着了。

　　要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出来的，对之后的问题没有影响。

**“未来与过去无关”，**这就是**无后效性**。

　　（严格定义：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。）

  


【最优子结构】

　　回顾我们对f(n)的定义：我们记“凑出n所需的**最少**钞票数量”为f(n).

　　f(n)的定义就已经蕴含了“最优”。利用w=14,10,4的**最优**解，我们即可算出w=15的**最优**解。

　　大问题的**最优解**可以由小问题的**最优解**推出，这个性质叫做“最优子结构性质”。

  


　　引入这两个概念之后，我们如何判断一个问题能否使用DP解决呢？

  


**能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。**

## 3. DP的典型应用：DAG最短路  
　　问题很简单：给定一个城市的地图，所有的道路都是单行道，而且不会构成环。每条道路都有过路费，问您从S点到T点花费的最少费用。

![]((20190303)什么是动态规划Dynamic_Programming动态规划的意义是什么_阮行止/v2-38e9a487997d2eea979097fbc9e9e674_r.jpg)  
一张地图。边上的数字表示过路费。  
  
　　这个问题能用DP解决吗？我们先试着记从S到P的最少费用为f(P).  
　　想要到T，要么经过C，要么经过D。从而$f(T)=\min⁡\{f(C)+20,f(D)+10\}$.

　　好像看起来可以DP。现在我们检验刚刚那两个性质：  
　　- 无后效性：对于点P，一旦f(P)确定，以后就只关心f(P)的值，不关心怎么去的。  
　　- 最优子结构：对于P，我们当然只关心到P的最小费用，即f(P)。如果我们从S走到T是 $S \to P\to Q\to T$ ，那肯定S走到Q的最优路径是 $S\to P\to Q$ 。对一条最优的路径而言，从S走到**沿途上所有的点（子问题）**的最优路径，都是这条大路的一部分。这个问题的最优子结构性质是显然的。

　　既然这两个性质都满足，那么本题可以DP。式子明显为：

$f(P)=\min⁡\{f(R)+w_{R→P}\}$

　　其中R为有路通到P的所有的点， $w_{R→P}$ 为R到P的过路费。

　　代码实现也很简单，拓扑排序即可。

## 4. 对DP原理的一点讨论  
【DP的核心思想】

　　DP为什么会快？  
　　无论是DP还是暴力，我们的算法都是在**可能解空间**内，寻找**最优解**。

　　来看钞票问题。暴力做法是枚举所有的可能解，这是最大的可能解空间。  
　　DP是枚举**有希望成为答案的解**。这个空间比暴力的小得多。

　　也就是说：DP自带剪枝。

　　DP舍弃了一大堆不可能成为最优解的答案。譬如：  
　　15 = 5+5+5 被考虑了。  
　　15 = 5+5+1+1+1+1+1 从来没有考虑过，因为这不可能成为最优解。

　　从而我们可以得到DP的核心思想：**尽量缩小可能解空间。**

　　在暴力算法中，可能解空间往往是指数级的大小；如果我们采用DP，那么有可能把解空间的大小降到多项式级。

　　一般来说，解空间越小，寻找解就越快。这样就完成了优化。

  


【DP的操作过程】

　　一言以蔽之：**大事化小，小事化了。**

　　将一个大问题转化成几个小问题；  
　　求解小问题；  
　　推出大问题的解。

【如何设计DP算法】

　　下面介绍比较通用的设计DP算法的步骤。

　　首先，把我们面对的**局面**表示为x。这一步称为**设计状态**。  
　　对于状态x，记我们要求出的答案(e.g. 最小费用)为f(x).我们的目标是求出f(T).  
**找出f(x)与哪些局面有关（记为p）**，写出一个式子（称为**状态转移方程**），通过f(p)来推出f(x).

【DP三连】

　　设计DP算法，往往可以遵循DP三连：

　　我是谁？ ——设计状态，表示局面  
　　我从哪里来？  
　　我要到哪里去？ ——设计转移

　　设计状态是DP的基础。接下来的设计转移，有两种方式：一种是考虑我从哪里来（本文之前提到的两个例子，都是在考虑“我从哪里来”）；另一种是考虑我到哪里去，这常见于求出f(x)之后，**更新能从x走到的一些解**。这种DP也是不少的，我们以后会遇到。

　　总而言之，“我从哪里来”和“我要到哪里去”只需要考虑清楚其中一个，就能设计出状态转移方程，从而写代码求解问题。前者又称pull型的转移，后者又称push型的转移。（这两个词是 [@阮止雨](https://www.zhihu.com/people/31585b1079521ef37391925a95a5d4ba) 妹妹告诉我的，不知道源出处在哪）


> 思考题：如何把钞票问题的代码改写成“我到哪里去”的形式？  
> 提示：求出f(x)之后，更新f(x+1),f(x+5),f(x+11).

## 5. 例题：最长上升子序列  
　　扯了这么多形而上的内容，还是做一道例题吧。

　　最长上升子序列（LIS）问题：给定长度为n的序列a，从a中抽取出一个子序列，这个子序列需要单调递增。问最长的上升子序列（LIS）的长度。  
　　e.g. 1,5,3,4,6,9,7,8的LIS为1,3,4,6,7,8，长度为6。

  


　　如何设计状态（我是谁）？

　　我们记 $f(x)$ 为以 $a_x$ 结尾的LIS长度，那么答案就是 $\max\{f(x)\}$ .

  


　　状态x从哪里推过来（我从哪里来）？

　　考虑比x小的每一个p：如果 $a_x>a_p$ ，那么f(x)可以取f(p)+1.  
　　解释：我们把 $a_x$ 接在 $a_p$ 的后面，肯定能构造一个以 $a_x$ 结尾的上升子序列，长度比以 $a_p$ 结尾的LIS大1.那么，我们可以写出状态转移方程了：

$f(x)=\max_{p<x , a_p<a_x }⁡\{f(p)\}+1$

　　至此解决问题。两层for循环，复杂度 $O(n^2)$ .

![]((20190303)什么是动态规划Dynamic_Programming动态规划的意义是什么_阮行止/v2-73ea19922aaac11c15dff9146a5c5b41_r.jpg)  
　　从这三个例题中可以看出，DP是一种思想，一种“大事化小，小事化了”的思想。带着这种思想，DP将会成为我们解决问题的利器。

　　最后，我们一起念一遍DP三连吧——我是谁？我从哪里来？我要到哪里去？

## 6. 习题  
如果读者有兴趣，可以试着完成下面几个习题：

一、请采取一些优化手段，以 $O(n\log n)$ 的复杂度解决LIS问题。

提示：可以参考这篇博客 [Junior Dynamic Programming--动态规划初步·各种子序列问题](https://pks-loving.blog.luogu.org/junior-dynamic-programming-dong-tai-gui-hua-chu-bu-ge-zhong-zi-xu-lie)

二、“按顺序递推”和“记忆化搜索”是实现DP的两种方式。请查阅资料，简单描述“记忆化搜索”是什么。并采用记忆化搜索写出钞票问题的代码，然后完成[P1541 乌龟棋 - 洛谷](https://www.luogu.org/problemnew/show/P1541) 。

三、01背包问题是一种常见的DP模型。请完成[P1048 采药 - 洛谷](https://www.luogu.org/problemnew/show/P1048)。

  


谢谢您看完本文 ⁄(⁄ ⁄ ⁄ω⁄ ⁄ ⁄)⁄

2019.3.3