给你一个整数数组

分析子问题当所有的子问题都是最优的时候总问题也就达到了最优。

分析最终状态以示例1为例子在选到5的时候刚好满足金额等于amount同时数量最优分析去掉最后一个问题的状态

amount

5可以发现这个问题可以像递归搜索树一样进行拆分又继续分析去掉倒数第二个问题的状态。

那么我们来分析代码

};我们的思路就是让它凑出的每一个amount之前的数值都满足最小硬币的需求那么当它递推到amount的时候它的每一个子问题都是最优的那么总问题就是最优的了。

for

coins[i]));}我们不断地往下搜索直到amount被减到0其中每一个分支都进行了min的处理所以当从下往上回溯的时候返回的就是每个分支就小的情况也是每个子问题最优的情况。

我们从凑出1块2块3块…知道amount块钱每一次我们都考虑凑出的硬币数量最少那么当我们推到amount的时候不就是最优了吗

class

};dp数组中的每个元素都被初始化为比amount大的数字我们每次都更新凑得钱数所需硬币的最小值从1凑到amount这样到了amount的时候就是最优的答案了

leetcode

个元素结尾的等差子数组数目取决于当前差值是否与前一个差值相等。

i-1

3无法形成等差子数组。

23111差值相等形成一个新的等差子数组

[1,

3无法形成等差子数组。

25221差值相等形成一个新的等差子数组

[1,

{public://x表示当前以nums[x]为结尾的数组int

dfs(int

numberOfArithmeticSlices(vectorint

nums){int