贪心思想

剑指 Offer 14- I. 剪绳子

方法一：动态规划
题解思路：对于正整数n，当n>=2时，可以拆分成至少两个正整数的和，令k是拆分出的令 k 是拆分出的第一个正整数，则剩下的部分是 n−k，n−k 可以不继续拆分，或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。
dp数组的含义： dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积。
边界条件： 0 不是正整数，1 是最小的正整数，0 和 1 都不能拆分，因此 dp[0]=dp[1]=0。
状态转移方程：
当 i≥2 时，假设对正整数 i 拆分出的第一个正整数是 j（1≤j1、将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j×(i−j)；
2、将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]。
因此，当 j 固定时，有 dp[i]=max(j×(i−j),j×dp[i−j])。由于 j 的取值范围是 1 到 i−1，需要遍历所有的 j 得到 dp[i] 的最大值，因此可以得到状态转移方程如下：

dp[i]= max_{1≤j<i} {(j×(i−j),j×dp[i−j])}

最终得到 dp[n] 的值即为将正整数 n 拆分成至少两个正整数的和之后，这些正整数的最大乘积。
通过代码可以知道其实是有着三个最优解的判断。

   public int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i-j), j * dp[i - j]));
            }
        }
        return dp[n];
    }

剑指 Offer 63. 股票的最大利润

题解思路：使用贪心策略，假设第i轮进行卖出操作， 买入的价格应该是在i之前并且价格最低。因此遍历数组时记录当前最低的买入价格，并且尝试将每个位置都作为卖出价格，取收益最大的即可。

股票买卖涉及两个状态，买入以及卖出，买入要是最低的卖出要是最高的。

动态规划解析：

• 状态定义： 设动态规划列表 dp，dp[i] 代表以 prices[i] 为结尾的子数组的最大利润（以下简称为 前 i 日的最大利润 ）。
• 转移方程： 由于题目限定 “买卖该股票一次” ，因此前 i 日最大利润 dp[i] 等于前i−1 日最大利润dp[i−1] 和第 i 日卖出的最大利润中的最大值。

  前 i 日最大利润 = max(前 (i-1) 日最大利润, 第 i 日价格 - 前 i 日最低价格) dp[i]=max(dp[i−1],prices[i]−min(prices[0:i]))

• 初始状态： dp[0] = 0 ，即首日利润为 00 ；
• 返回值： dp[n - 1] ，其中 n 为 dp 列表长度。

  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;
    }

  总结： 对于当日的选择只有两种：要么在前一天将股票卖出，要么在当日将股票卖出