算法分享（贪心+动态规划）
算法解决问题的方法。就好比同样是从长沙到北京，坐火车可能需要几天，坐高铁6小时，坐飞机两个半小时，当然交通工具不同，所消耗的成本也不同，算法就是在成本与时间中不断权衡，一个好的算法衡量标准就是用尽可能小的代价成本实现较短时间到达。
算法有什么用？
<ul>面试大厂必备技能。
更快的性能。计算机中主要的计算组件就是CPU，假设某个问题可以通过两种算法(简称为算法1、算法2)解决，它们的时间复杂度分为O(n)和O(n²)，假设现在某型号CPU的运算速度提升了10倍，我们分别配置稍微低一点的CPU去跑时间复杂度为O(n)的算法，和使用提升了10倍的CPU去跑时间时间复杂度为O(n²)的算法，我们会发现一个结果：在n>10以后，使用配置低的硬件运行的效率要比配置高的硬件效率更好（假设n=20, CPU1: 20 10.50.2130->60.230->50.1820->50.25先兑换20->5，再兑换50->11，得15.5个兴币
动态规划(递归+存储)
2030405060708050->10.500010.510.510.510.530->606610.510.510.516.530->506610.5111116.520->5566111115.516.5寻找递推关系式
面对当前场次有两种可能性：
小兴兴余额不足，总兴币与上一个场次兴币个数一致
小兴兴满赠门槛，但兑换了当前场次不一定是当前最优，所以需判断兑换的兴币是不是最大值
关键代码：
int[] w = { 0 , 50 , 30 ,30 , 20 }; //小兴兴兑换值0、50、30、30、20
float[] v = { 0 , 10.5f , 6 , 5 , 5 }; //兴币面额 10.5、6、5、5
int balance= 80; //用户小兴兴总余额
float[][] dp = new float; //动态规划表
for (int i = 1; i <= 4; i++) {
for (int j = 20; j <= balance ; j+=10) {
if (j < w){
dp = dp;
} else{
dp = Math.max(dp, dp] + v);
}
}
}关键代码
for (int i = 1; i
页:
[1]