算法Day2—动态规划（剑指offer63+01背包问题(1)）

剑指offer63：股票的最大利润

题目：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

转移方程：dp[i] = max(dp[i−1], 第i日卖出的最大利润中的最大值)

class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit=0;
        for(int price : prices){
            cost = Math.min(cost,price); //记录更新最小值
            profit = Math.max(profit,price-cost); //转移方程比较最大利润
        }
        return profit;
    }
}

 LCR 188. 买卖芯片的最佳时机 - 力扣（LeetCode）

01背包问题（1）

问题：有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

状态变量：dp[i][j] 表示前 i 件物品放入容量为 j 的背包的最大价值。（j为已用容量）

有两种选择：

1. 不放入：dp[i][j] = dp[i-1][j]，即物品 i 的重量大于背包 j 的重量
2. 放入：则上一步的状态为 dp[i-1][j-weight[i]]，当前状态 dp[i][j] = dp[i-1][j-weight[i]] + value[i]

递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

递推和递归的区别：

递归：在一个函数的定义中又直接或间接地调用本身

递推：用若干步可重复运算来描述复杂问题的方法。

边界：dp[0][j]：存放编号为 0 的物品，容量为 j 的背包所能存放的最大价值

        当 j < weight[0] 时，dp[0][j] = 0

        当 j >= weight[0] 时，dp[0][j] = value[0]

（未完待续...）

JAVA常识

Integer.MAX_VALUE

int m = Integer.MAX_VALUE //表示int数据类型的最大取值数：2 147 483 647

 if判断

if(布尔表达式){

        //如果布尔表达式的值为true

}else{

        //如果布尔表达式的值为false

}

 for循环（2）

for (循环变量类型 循环变量名称 : 要被遍历的对象) 循环体