[//]: # 最简单的01背包问题（C语言）

二维代码

#include <stdio.h>
#include <stdlib.h>

#define N 1010

int n, m;       // n为物品，m为背包体积
int v[N], w[N]; // v是对应物品体积，w是对应物品价值（权重，重量）
int f[N][N];    // dp的数组

int main()
{

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d", &v[i], &w[i]);
    }

    for (int i = 1; i <= n; i++)     // 遍历物品
        for (int j = 0; j <= m; j++) // 遍历体积
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i])
                f[i][j] = f[i][j] >= f[i - 1][j - v[i]] + w[i] ? f[i][j] : f[i - 1][j - v[i]] + w[i];
        }

    printf("%d\n", f[n][m]);
    return 0;
}
*/

代码的巧妙地方

首先解释一下这个代码，最开始看视频的时候已经不知道f[][]是什么东西了，纠结于具体问题这个f应该怎么才能做出动态规划

解释完做基本的f二维数组里边存的是什么之后，看看代码
视频中在对全局变量进行创建的时候使用的是const int N中的N，但是C语言中const 就是用来限定一个变量不允许被改变的修饰符，即只读变量，因为占有存储空间，所以编译器不知道编译时的值，所以就不知道该给数组定义多大的。
C++中不存在这个问题
如果按const int N 来定义数组大小的话会报错 error:variably modified ‘v’ at file scope
所以用了#define

还有全局变量会自动初始化为0
c99标准：
If an object that has automatic storage duration is not initialized explicitly, its value isindeterminate. If an object that has static storage duration is not initialized explicitly,then:
— if it has pointer type, it is initialized to a null pointer;
— if it has arithmetic type, it is initialized to (positive or unsigned) zero;
— if it is an aggregate, every member is initialized (recursively) according to these rules;
— if it is a union, the first named member is initialized (recursively) according to theserules.

代码中
for (int i = 1; i <= n; i++) // 遍历物品 for (int j = 0; j <= m; j++) // 遍历体积
在循环的变量范围，首先i代表背包里选择1~i件物品放，这里一开始i初始化为1就是选1~1件，即1件，一直到最后i=n就是选择1~n件物品放入背包，这样从1开始也可以避免f[i-1][]当i=0的时候变成f[-1][]的出界问题，f[1][]可以直接从已经自动初始化的f[0][]进行计算
j需要从背包体积为0一直计算到背包的总体积m

算法整体思路见视频

一维代码

#include <stdio.h>
#include <stdlib.h>

#define N 1010

int n, m;       // n为物品，m为背包体积
int v[N], w[N]; // v是对应物品体积，w是对应物品价值（权重，重量）
int f[N];    // dp的数组

int main()
{

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d", &v[i], &w[i]);
    }

    for (int i = 1; i <= n; i++)     // 遍历物品
        for (int j = m; j >= v[i]; j--) // 遍历体积
        {

                f[j] = f[j] >= f[j - v[i]] + w[i] ? f[j] : f[j - v[i]] + w[i];
        }

    printf("%d\n", f[m]);
    return 0;
}

一维代码使用了滚动数组
这里我理解的就是之前的状态计算方程是f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i])，这里边可以看出来第i行的dp数组仅仅与前一行有关
计算结果的保存都用一个一维数组就够了，所以dp数组f[][]中只剩下f[j]就够了

比如要算第二行的时候有第一行的数据就行了，算出来第二行后第一行可以丢掉了，通过第二行继续算第三行，这样其实只需要一维数组就行了

因为之前二维数组计算max的时候都需要f[i-1][j-v[i]]+w[i]与f[i-1][j]进行比较，f[i-1][j]也就是与前一行的这列的数，所以把前一行算出来的结果（一维）看作后一行的没比较的数据（一维），再通过这个一维的数据进行对应行的计算
假设这里一维的计算是之前二维计算时通过第二行的结果算第三行，目前的一维数组是第二行（i=2）的结果（一维），可以先将它当作第三行没比较之前的数（一维），然后通过现在没比较过的第三行的数据（其实就是第二行的数据，i=2）计算i=3时的f[j-v[i]]+w[i]（也就是之前二维数组i=3时的f[i-1][j-v[i]]+w[i]），再与第二行的结果比较大小存入数组
这里的难点在于为什么j循环里边是倒着算的

786 第k个数

C 代码（最终版）

这个代码实在看完他人的题解之后做出来的，比我自己的第一次的代码整洁而且简单优美

#include<stdio.h>
#define Maxsize 100000

int k_num(int a[],int l,int r,int k)
{
    if(l>=r)return a[l];
    int i = l-1, j = r+1, x = a[l+r>>1];
    while(i<j)
    {
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j)
        {
            int t;
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    if(k<=j)return k_num(a,l,j,k);
    else return k_num(a,j+1,r,k);
}

int main()
{
    int n,k,res;
    int a[Maxsize];
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    res = k_num(a,0,n-1,k-1);
    printf("%d\n",res);
    return 0;
}

不论是这个代码还是下边第一次我做题时候的代码，让我感觉困难的都是边界判断部分
首先上方的这个代码，主函数部分可以看出来传进去的第k个小的数是k-1的参数，也就是数组下标
这个操作可以简化k的计算流程（在下边解释）

整体的思路就是当最后递归到只有一个数的时候，因为其他的小于等于和大于等于它的都分到了另外两侧，这个单个的一个数的下表不会被没排完的顺序所影响，因为它已经确定就在这个位置了，那么这个数就很自然的是我们要找的第k个数，返回就行了
不需要在中间进行除了快排之外的判断

    if(k<=j)return k_num(a,l,j,k);
    else return k_num(a,j+1,r,k);

接下来解释这两行最精华的部分
当while语句块执行完之后，j>=i（当i=j的时候就是奇数个排序的数字，i和j都走到数组的中间，也就是取的x=a[l+r>>1]的地方）
不论j>i还是j=i，i左侧的都是<=x的数，j右侧的都是>=x的数，在快排模板中，我们使用了j作为分界线
在这里也一样统一用j作为分界线
如果k<=j，这时记住k不是第几个，而已经变成了下标，这种情况说明数组下标从最左侧l到j的这一部分都满足<=x的部分中有我们要找的下标为k的这个数（如果i=j这时候a[j]=x，上文前三行已分析，下标从最左侧l到j的这一部分都满足<=x，另外一种当i<j的时候显然更满足），那么递归下去在这个区间继续j找
如果不是就在另外一个区间找

递归我感觉就是要装作糊涂一点，我以前总喜欢一步一步推到最后一个返回的过程，但是就把自己绕进去了，其实像这个就是一句话的事：要是左侧<=x的数中包含下标k就继续找这个区间，否则去另外一个区间找。思维上能走通，代码上能体现出大局观就行，因为这时已经对了，不用自己再去试几组数然后带进去验证总结一般规律。

C 代码（第一次的版本）

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define Maxsize 100000

int k_num(int a[], int l, int r, int k)
{
    if (k > (r-l + 1))return -1;
    if (l >= r) return a[l];
    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while (i < j)
    {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j)
        {
            int t;
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    if (i == j) {
        if (j - l + 1 == k)return a[j];
    }
    if (j - l + 1 < k)return k_num(a, j + 1, r, k-(j-l+1));
    else return k_num(a, l, j, k);

}

int main()
{
    int n, k, res;
    int a[Maxsize];
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    res = k_num(a, 0, n - 1, k);
    printf("%d\n", res);
    return 0;
}

我第一次的做法很笨，直接就是找的k是第几个数，而不是下标
还是一样，返回的时候如果只剩一个那肯定就是它了，不过也能在中间进行返回，也就是递归没有走到最后的时候

    if (i == j) {
        if (j - l + 1 == k)return a[j];
    }
    if (j - l + 1 < k)return k_num(a, j + 1, r, k-(j-l+1));
    else return k_num(a, l, j, k);

主要就是这几行
首先我是将while语句块走完之后i和j的位置分为了i=j和i[HTML_REMOVED]=它，如果这个数相对于左侧界限l刚好是第k个数，那么就是我们要找的数
如果不是，那么就在左侧或者右侧，这时候不用再分i和j的位置关系，如果j - l + 1 < k，也就是判断j这个指针相对于数组起始第几个的数<k，那么左侧这部分<=x的数里边没有要找的第k个数
这时候要找右侧，将k传参传为k-(j-l+1)，也就是右侧第几小，所以这个算的时候就是整体第几小的k减去左侧一共多少个数就是右侧第几小
否则就在左侧正常找就行

785.快速排序 代码注意部分

C++ 代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define Maxsize 100000

void quick_sort(int a[], int l, int r)
{
    if (l >= r)return;
    int i = l - 1, j = r + 1, x = a[l + r >> 1]; //这里注意右移一位代表除以2，如果写为>>2，那么x可能在判断的数组范围之外比较错误，从而导致排序错误
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) {
            int t;
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        //这里如果写成swap函数需要使用指针传参，否则a数组内部不会改变
    }
    //while完成之后i左侧全都<=x，j右侧全都>=x
    quick_sort(a, l, j);//注意右边界是j
    quick_sort(a, j + 1, r);
}

int main() {
    int n;
    int a[Maxsize];
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    quick_sort(a, 0, n - 1);
    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}