动态规划

动态规划题目特点

计数
- 有多少种方式走到右下角
- 有多少中方法选出k个数使得和为Sum
求最大最小值
- 从左上角走的右下角路径上数字和的最大值
- 最长上升子序列长度
求存在性
- 取石子游戏,先手是否必胜
- 能不能选出k个数使得和为Sum

动态规划组成部分

确定状态

最后一步
子问题

比如买/不买。使用2元/5元/7元硬币等等，都对应一个状态f(x)

转移方程

确定f(x)的公式，如凑硬币问题：

$$f(x) = min\{f(x-2),f(x-5),f(x-7)\}$$

$$f[x] = min\{f[x-2],f[x-5],f[x-7]\}$$

初始条件和边界条件

何时（何种状态）初始化？何时（何种状态）无解？如凑硬币问题：

f[0] 状态初始化。
f[负数] 状态无解。

计算顺序

如凑硬币问题：

f[0],f[1],f[2]......

补充 - 凑硬币问题

你有3种硬币: 2r 5r 7r (硬币足够多)
买一个物品 n 元
如何用最少的硬币正好付清,不需要对方找钱?

这个是我写的代码,应该没啥问题:

#include<stdio.h>
#include<stdlib.h>
#define COIN_2 2
#define COIN_5 5
#define COIN_7 7
#define INT_MAX 114514

int min(int a,int b,int c); // 求最小值
int f(int n,int fres[]); // 求使用coin时的最少硬币数

int main(){
    int n = 0; // 需要付的钱
    scanf("%d",&n);
    int fres[n+1]; // 创建结果表 
    int i;
    for(i = 0; i < n+1; i++){
        fres[i] = 0;
    }
    int result = f(n,fres); // 开始计算
    if(result != INT_MAX){ // 判断是否有解
        printf("需要%d个硬币\n",result);
    }else{
        printf("无解\n");
    }
    return 0;
}

int min(int a,int b,int c){
    if(a == -1) a = INT_MAX;
    if(b == -1) b = INT_MAX;
    if(c == -1) c = INT_MAX;
    int min = a;
    min = min<b?min:b;
    min = min<c?min:c;
    return min;
}

int f(int n,int fres[]){
    if(n ==  0){ // 如果金额为0就只需要0个硬币
        return 0;
    }else if(n < 0){
        return -2;
    }
    if(fres[n] == 0) fres[n] = min(f(n-COIN_2,fres)+1,f(n-COIN_5,fres)+1,f(n-COIN_7,fres)+1);
    // 返回结果(最后一次使用2元/5元/7元硬币分别对应的需要的硬币数的最小值)
    return fres[n];
}

动态规划