兑换零钱（一）（动态规划）

题意

给定一个正整数数组，和一个目标值，问最少选取多少个数组中的值能使得其和等于目标值。其中每个值可以被选任意次

思路分析

最优关系的数学推导

假设对于值aim有一个最优方案，这个最优方案中有选一次x,那么

上述最优方案中去掉x的剩余的数，是aim-x的一个最优方案。

证明：

反证法，如果去掉x后不是aim-x的最优方案，也就是存在更优的方案，让aim-x有更少数量的构成，那么对于这个让aim-x有更少数量构成的方案，加上x,也会让aim有更优方案。与初始方案是aim的最优方案矛盾

综上, 一个最优方案，一定是由某个最优方案，加上某个值得到的

转换成表达式

这里我们不关心具体方案，只关心构成的个数

因此设cnt[i] 表示构成i的最优方案的个数

v 是给定数组中的其中一个值

根据上面的结论，有依赖关系

cnt[i] = 1 + min(for(v:arr) cnt[i-v]);

递归转递推

上面计算每个i依赖于比它更小的值，而比它更小的值应该更早完成计算

所以考虑把关系反置，当完成一个计算后，去更新比当前值更大的值

for(v:arr){
	cnt[i+v] = min(cnt[i+v], cnt[i] + 1);
}

边界处理

这里有两种边界需要处理。

1. 加和后超过了要求的目标。这种值运算结果对我们要求的内容没有意义，直接忽略掉

if(i+v > aim) break/continue;

2. 无法达到的值

虽然题目说无法达到的值输出负1，但是如果直接用-1表示，那么加和运算又需要做-1的相关判断

因为要求最小值，这里如果一个无法达到的值我们用无穷大表示，那么无穷大+1依然能以参与运算，而整数里不提供直接的无穷大，考虑用0x3f3f3f3f来表示无穷大。

用0x3f3f3f3f表示无穷大后有一些好的性质

const int INF = 0x3f3f3f3f;
INF == min(INF,INF+INF); // 可相加不会溢出
v == min(v,INF); // 可参与比较
v == min(v,INF+1); // 可参与运算和比较

需要注意的是，输出时还是有-1的处理

题解

所以整合上面的内容，先枚举奇偶，再枚举中心，再枚举长度。这样就能计算出最长回文串的长度

class Solution {
public:
    /**
     * 最少货币数
     * @param arr int整型vector the array
     * @param aim int整型 the target
     * @return int整型
     */
    int minMoney(vector<int>& arr, int aim) {
        const int INF = 0x3f3f3f3f; // 无穷大
        vector<int> cnt(aim+1,INF); // 状态 金额与消耗的个数
        cnt[0] = 0;
        for(auto v:arr){
            for(int i = 0;i < aim;i++){
                if(i+v > aim) break; // 超过目标
                cnt[i+v] = min(cnt[i+v],cnt[i] + 1);
            }
        }
        return cnt[aim] == INF ? -1 : cnt[aim];
    }
};

复杂度分析

时间复杂度: 先遍历数组，后遍历所有小于目标的值，所以总时间复杂度为$O(n\cdot aim)O(n\; \backslash cdot\; aim)$

空间复杂度: 用来记录状态的数组和目标的值大小相关，所以空间复杂度为$O(aim)O(aim)$