动态规划

  1. 确定base case
  2. 状态和选择
  3. dp数组/函数的定义
  4. 寻找状态间的关系

注意

  1. 一般用来求最值.
  2. 子序列和子数组,子串分清楚
  3. 至少有一个不在最长公共子序列中max((dp(i -1),j),dp(i,j-1);
  4. 注意要求的返回值
  5. 使用函数记得备忘录

确定base case

  1. 不止边界条件,还应该有失败条件

    eg:零钱问题,最终n < 0;表示没合适的硬币凑出相对应的金钱.

  2. 可能需要for循环赋值eg:编辑距离

选择

  1. 题目给的明显的选择

  2. 要不要,装不装,打不打……

  3. 开始另立门户

    eg:最大子数组,memo[i] = Math.max(nums[i],memo[i - 1]+nums[i]);

  4. 两个指针一般从里到外

状态

  1. 单个状态
  2. 前i个状态
  3. 两个指针

背包问题

定义dp数组时数量在前

1
2
3
4
5
6
7
8
9
10
11
12
13
14
       
for(int i = 1;i <= n;i++){
            for(int j = 1;j <= V;j++){
                //当i = n - 1时,j循环时就代表剩余空间大小
                //eg:j = V表示的是前边一个没装
                if(vw[i - 1][0] > j){
                dp[i][j] = dp[i - 1][j];
            }else{
                    int a = dp[i-1][j-vw[i - 1][0]]+vw[i - 1][1];
                    int b = dp[i-1][j];
                dp[i][j] = Math.max(a,b);
            }
            }
        }

环形数组

想着怎么化成子问题,分情况