有1,5,10,20,50面额的货币,使用尽量少的货币凑出66元.贪心算法50+10+5+14张为最优解.
如果面额为1,5,11,使用尽量少的货币凑出15元.贪心算法11+1+1+1+1,使用了5张,但3张为最优解.
f(15)=f(14)+1=5
f(15)=f(4)+1=5
给定一个三角形 triangle ,找出自顶向下的最小路径和.
每一步只能移动到下一行中相邻的结点上.相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点.也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 .
为每一步都选择最小的数,结果并不一定正确.
从上往下,求出到每个点的最短距离.