1. 状态抽象
  2. 状态如何转移

  3. 确定边界

    LeetCode

    19. 秋叶收藏集（LCP）

    给定一份秋叶收藏集（字符串），其中r表示红叶，y表示黄叶。每次可以把一片红叶替换成黄叶或者相反，求使得这份收藏集变成红黄红的排列。
    （1）三种状态
    普通DP - 图1：使得普通DP - 图2的字符串从成为全为红排列的最小改变次数。
    普通DP - 图3：使得普通DP - 图4的字符串从成为为红黄排列的最小改变次数。
    普通DP - 图5：使得普通DP - 图6的字符串从成为为红黄红排列的最小改变次数。
    （2）状态转移方程
    普通DP - 图7(i不是红叶)
    普通DP - 图8(i不是黄叶)
    普通DP - 图9(i不是红叶)
    （3）边界
    需要考虑普通DP - 图10或者普通DP - 图11处的情况
    发现空间是可以优化成O(1)的，将数组替换成三个状态变量即可，然后调转一下更新状态变量的顺序即可。优化后的时间复杂度是O(n)，空间复杂度为O(1)。 ```java public int minimumOperations(String leaves) { if (leaves == null || leaves.length() <= 2) return 0; int n = leaves.length(); int[][] state = new int[n][3]; //初始化边界 state[0][0] = (leaves.charAt(0) == ‘r’ ? 0 : 1); state[0][1] = state[0][2] = state[1][2] = 100000;

    for (int i = 1; i < n; i++) {

    1.  char leave = leaves.charAt(i);
    2.  state[i][0] = state[i-1][0] + (leave == 'r' ? 0 : 1);
    3.  state[i][1] = Math.min(state[i-1][0], state[i-1][1]) + (leave == 'y' ? 0 : 1);
    4.  state[i][2] = Math.min(state[i-1][1], state[i-1][2]) + (leave == 'r' ? 0 : 1);

    } return state[n-1][2]; }

public int minimumOperations(String leaves) { if (leaves == null || leaves.length() <= 2) return 0; int n = leaves.length(); int state0 = (leaves.charAt(0) == ‘r’ ? 0 : 1); int state1 = 100000, state2 = 100000; for (int i = 1; i < leaves.length(); i++) { char leave = leaves.charAt(i); state2 = Math.min(state1, state2) + (leave == ‘r’ ? 0 : 1); state1 = Math.min(state0, state1) + (leave == ‘y’ ? 0 : 1); state0 = state0 + (leave == ‘r’ ? 0 : 1); } return state2; }

  1. <a name="6cUAc"></a>
  2. #### [416. 分割等和子集](https://leetcode-cn.com/problems/partition-equal-subset-sum/)
  3. 首先想到的解法，穷举所有解使得数组和可以为一半，时间复杂度为O(2)，超时。就算进行剪枝也没什么意义，比如数组大小必须超过2、最大元素超过了数组和的一半等等。<br />本题其实是一个NP问题，要得到解不容易，但是验证一个解很简单，不应该想（输入规模）多项式时间复杂度的方法，比如先排序然后依次将每个元素添加到元素和更小子集的贪心算法都是错误的，应该尝试非多项式时间复杂度的算法，比如时间复杂度和元素大小相关的动态规划。
  4. ```java
  5. public boolean canPartition(int[] nums) {
  6.     if (nums == null)   return false;
  7.     int sum = 0;
  8.     for (int i = 0; i < nums.length; i++) {
  9.         sum += nums[i];
  10.     }
  11.     if ((sum & 1) == 1) return false;
  12.     return sum(nums, sum/2, 0);
  13. }
  14. private boolean sum (int[] nums, int target, int curIdx) {
  15.     if (target == 0)    return true;
  16.     if (curIdx == nums.length)  return false;
  17.     for (int i = curIdx; i < nums.length; i++) {
  18.         if (i > curIdx && (nums[i] == nums[curIdx]))    continue;
  19.         swap (nums, curIdx, i);
  20.         if (sum(nums, target-nums[curIdx], i+1)) {
  21.             return true;
  22.         }
  23.         swap(nums, curIdx, i);
  24.     }
  25.     return false;
  26. }
  27. private void swap (int[] nums, int i, int j) {
  28.     int temp = nums[i];
  29.     nums[i] = nums[j];
  30.     nums[j] = temp;
  31. }
  33. // 复杂度和数组元素大小相关
  34. public boolean canPartition(int[] nums) {
  35.     if (nums == null)   return false;
  36.     if (nums.length < 2)    return false;
  38.     int sum = 0, maxValue = nums[0];
  39.     for (int i = 0; i < nums.length; i++) {
  40.         sum += nums[i];
  41.         maxValue = Math.max(maxValue, nums[i]);
  42.     }
  43.     if ((sum & 1) == 1) return false;
  44.     if (maxValue > sum/2)   return false;
  46.     int target = sum / 2, n = nums.length;
  47.     boolean[] dp = new boolean[target+1];
  48.     //边界条件初始化
  49.     dp[0] = true;
  50.     for (int i = 0; i < nums.length; i++) {
  51.         int val = nums[i];
  52.         for (int j = target; j > 0; j--) {
  53.             if (val <= j) {
  54.                 dp[j] = dp[j] || dp[j-val]; 
  55.             }
  56.         }
  57.     }
  58.     return dp[target];
  59. }

状态dp(i)(j)表示[0, i]中可以选择若干数使得其和为j，那么相应的状态转移方程如下所示：
普通DP - 图12
然后可以发现二维dp可以优化成一维dp，代码如上所示。
时间复杂度为O(ntarget)，其中target为数组和的一半，即表示和输入元素大小有关。
空间复杂度为O(ntarget)，可以优化为O(target)。
其实第二层循环代码可以更加优雅，代码如下所示：

  1. for (int i = 0; i < nums.length; i++) {
  2.     int val = nums[i];
  3.     for (int j = target; j >= val; j--) {
  4.         dp[j] |= dp[j-val];
  5.     }
  6. }