1. dp[i] 第 i+1项的值
2. 确定递推公式 dp[i] = dp[i-1] + dp[i-2]
3. 初始化dp数组 dp[0]=1 dp[1]=1
4. 遍历顺序 从前向后遍历
5. 举例推到 第5项 即dp[5-1] dp[4]
value    1    1    2    3    5
index    0    1    2    3    4

public int Fibonacci(int n) {
    if (n <= 2) {
        return 1;
    } 
    int[] dp = new int[n];
    dp[0] = 1;
    dp[1] = 1;
    for (int i=2; i<n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n-1];
}

1.确定dp数组及下标的含义
dp[i] 跳第i+1个台阶的跳法
2.确定递推公式
dp[i] = dp[i-1] + dp[i-2]
3.初始化数组
dp[0] = 1 dp[2] = 2
4.确定遍历顺序
5.举例到第五个台阶
1 2 3 5 8
0 1 2 3 4

public int jumpFloor(int target) {
    if (target <= 2) {
        return target;
    }
    int[] dp = new int[target];
    dp[0] = 1;
    dp[1] = 2;
    for (int i=2; i<target; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[target-1];
    
}

public int climbStairs(int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return 1;
    }
    int pre1 = 1;
    int pre2 = 1;
    int current=-1;
    for (int i=2; i<=n; i++) {
        current = pre1 + pre2;
        pre1 = pre2;
        pre2 = current;
    }
    return current;
}

public int climbStairs(int n) {
    n++;
    double temp = ((Math.pow((1 + Math.sqrt(5)) / 2, n) - Math.pow((1 - Math.sqrt(5)) / 2, n)) / Math.sqrt(5));
    System.out.println(temp);
    int result = (int)temp;
    return result;
}

1. 确定dp[i] 到第i层楼梯的跳法
2. 递推公式 dp[i] = dp[i-1] + dp[i-2] + dp[0]
3. 初始化dp[0] = 1 从最底下直接跳到n层有1中方法
4. 遍历顺序，从前往后
5. 举例 5
1 1 2 4 8 16
0 1 2 3 4 5

public int jumpFloorII(int target) {
    int[] dp = new int[target+1];
    dp[0] = 1;
    for (int i=1; i<=target; i++) {
        dp[i] = this.getSum(dp, i);
    }
    return dp[target];
}

private int getSum(int[] dp, int i) {
    int sum = 0;
    for (int j=0; j<i; j++) {
        sum += dp[j];
    }
    return sum;
}

private int sum = 0;
public int jumpFloorII(int target) {
    int[] dp = new int[target+1];
    dp[0] = 1;
    for (int i=1; i<=target; i++) {
        dp[i] = this.getSum(dp, i);
    }
    return dp[target];
}

private int getSum(int[] dp, int i) {
    this.sum += dp[i-1];
    return this.sum;
}

public int jumpFloorII(int target) {
    /*
    1. 确定dp[i] 到第i层楼梯的跳法
    2. 递推公式 dp[i] = dp[i-1] + dp[i-2] + dp[0]
    3. 初始化dp[0] = 1 从最底下直接跳到n层有1中方法
    4. 遍历顺序，从前往后
    5. 举例 5
    1 1 2 4 8 16
    0 1 2 3 4 5
    */
    int[] dp = new int[target+1];
    dp[0] = 1;
    for (int i=1; i<=target; i++) {
        if (i==1) {
            dp[i] = dp[0];
        } else {
            dp[i] = 2 * dp[i-1];
        }
    }
    return dp[target];
}

public int FindGreatestSumOfSubArray(int[] array) {
    int result = Integer.MIN_VALUE; // 求最大，赋值最小，以免影响结果
    for (int i=0; i<array.length; i++) {
        int count = 0;
        for (int j=i; j<array.length; j++) {
            count += array[j];
            result = count > result ? count : result;
        }
    }
    return result;
}

public int FindGreatestSumOfSubArray(int[] array) {
    int result = Integer.MIN_VALUE;
    int count = 0;
    for (int i=0; i<array.length; i++) {
        count += array[i];
        // 记录最大值
        if (count > result) {
            result = count;
        }
        // 如果是负数，重新累加
        if (count < 0) count = 0;
    }
    return result;
}

  1. 确定dp数组含义
  dp[i] 包括下标i之前的最大连续子序列和为dp[i] 注意，是必须包括i的连续序列
  2. 确定递推公式
  只有两种方法得到dp[i] dp[i-1] + num[i] 还有num[i]
  dp[i] = max{dp[i-1]+num[i], num[i]}
  dp[i-1] 前i-i连续子序列最大值，num[i] 当前数组元素的值
  3. 初始化数组
  dp[0] = num[0]
  4. 遍历方向，从前向后
  5.举例 [1,-2,3,10,-4,7,2,-5]
  1 -1 3 13 9 16 18 13

public int FindGreatestSumOfSubArray(int[] array) {
    int[] dp = new int[array.length];
    dp[0] = array[0];
    int result = array[0];
    for (int i=1; i<array.length; i++) {
        dp[i] = Math.max(dp[i-1]+array[i], array[i]);
        result = dp[i] > result ? dp[i] : result;
    }
    return result;
}

1. dp[i][0] 以num[i] 结尾的之前的子序列最大和
   dp[i][1] 以num[i] 结尾的之前最大和子序列开始的索引
2. 由于是num[i] 结尾要么包含num[i-1] 要么不包含num[i-1]
   dp[i] = max{dp[i-1]+num[i], num[i]}
3. 初始化 dp[0][0] = num[0] dp[0][1] = 0
4. 从前向后
5. 举例  [1,-2,3,10,-4,7,2,-5]
    dp[i][0] 1 -1 3 13 9 16 18 13
    dp[i][1] 0  0 2  2 2  2  2  2

import java.util.*;
public class Solution {
    public int[] FindGreatestSumOfSubArray (int[] array) {
        // write code here
        int[][] dp = new int[array.length][2];
        dp[0][0] = array[0];
        dp[0][1] = 0;
        int startIndex = 0;
        int maxSum = dp[0][0];
        for (int i=1; i<array.length; i++) {
            if (array[i] > dp[i-1][0]+array[i]) {
                dp[i][0] = array[i];
                startIndex = i;
            } else {
                dp[i][0] = array[i] + dp[i-1][0];
            }
            if (dp[i][0] > maxSum) {
                maxSum = dp[i][0];
            }
            dp[i][1] = startIndex;
        }
        for (int i=0; i<array.length; i++) {
            System.out.println(dp[i][0] + " " + dp[i][1]);
        }
        int maxLength = 0;
        int endIndex = 0;
        for (int i=0; i<array.length; i++) {
            if (dp[i][0]==maxSum && i+1-dp[i][1]>maxLength) {
                startIndex = dp[i][1];
                endIndex = i+1;
            }
        }
        return Arrays.copyOfRange(array, startIndex, endIndex);
    }
}

public int[] FindGreatestSumOfSubArray (int[] array) {
    int length = array.length;
    int[] dp = new int[length];
    dp[0] = array[0];
    int maxSum = dp[0];
    for (int i=1; i<length; i++) {
        dp[i] = Math.max(dp[i-1]+array[i], array[i]);
        maxSum = Math.max(maxSum, dp[i]);
    }
    int startIndex = 0, endIndex = 0, maxLength=0;
    for (int i=0; i<length; i++) {
        if (dp[i] == maxSum) {
            // dp中寻找前面离得最近的负数
            int j;
            for (j=i-1; j>=0; j--) {
                if (dp[j] < 0) {
                    break;
                }
            }
            if (i-j>maxLength) {
                startIndex = j + 1;
                endIndex = i + 1;
            }
        }
    }
    return Arrays.copyOfRange(array, startIndex, endIndex);
}

1. dp[i] 能放下i个小木板的矩形，小木板的放法
2. dp[i] = dp[i-1] + dp[i-2]
在i-1放法后面都竖着放一块，在i-2后面都横着放两块
3. dp[0] = 1 dp[1] = 1 
根据题目给的条件dp[0]应该为0，但是为了使dp[2] = dp[0] + dp[1]成立，故使dp[0] = 1
4. 前至后遍历
5. 举例 n=5
1 1 2 3 5 8
0 1 2 3 4 5

public int rectCover(int target) {
    if (target == 0) {
        return 0;
    }
    int[] dp = new int[target+1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i=2; i<=target; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[target];
}

public int maxProfit (int[] prices) {
    // write code here
    if (prices.length == 0) {
        return 0;
    }
    int[][] dp = new int[prices.length][2];
    dp[0][0] = -prices[0];
    dp[0][1] = 0;
    for (int i=1; i<prices.length; i++) {
        dp[i][0] = Math.max(-prices[i], dp[i-1][0]);
        dp[i][1] = Math.max(prices[i]+dp[i-1][0], dp[i-1][1]);
    }
    return dp[prices.length-1][1] > 0 ? dp[prices.length-1][1] : 0; 
}

public int maxProfit(int[] prices) {
    int length = prices.length;
    int[][] dp = new int[length][2];
    dp[0][0] = - prices[0];
    dp[0][1] = 0;
    for (int i=1; i<length; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]-prices[i]);
        dp[i][1] = Math.max(dp[i-1][0] + prices[i], dp[i-1][1]);
    }
    return dp[length-1][1];
}

public int maxProfit(int[] prices) {
    if (prices.length == 1) {
        return 0;
    }
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    temp.add(prices[0]);
    for (int i=1; i<prices.length; i++) {
        if (prices[i] > prices[i-1]) {
            temp.add(prices[i]);
        } else {
            list.add(new ArrayList<>(temp));
            temp.clear();
            temp.add(prices[i]);
        }
    }
    list.add(temp);
    List<Integer> profit = new ArrayList<>();
    for (List<Integer> item : list) {
        if (item.size() <= 1) {
            continue;
        }
        profit.add(item.get(item.size()-1) - item.get(0));
    }
    if (profit.size() == 0) {
        return 0;
    } else if (profit.size() == 1) {
        return profit.get(0);
    } else {
        Collections.sort(profit);
        return profit.get(profit.size()-1) + profit.get(profit.size()-2);
    }
}

public int maxProfit(int[] prices) {
    int length = prices.length;
    int[][] dp = new int[length][6];
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    dp[0][2] = 0;
    dp[0][3] = -prices[0];
    dp[0][4] = 0;
    for (int i=1; i<length; i++) {
        dp[i][0] = dp[i-1][0];
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);
        dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1]+prices[i]);
        dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2]-prices[i]);
        dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3]+prices[i]);
    }
    return dp[length-1][4];
}

public int maxProfit(int k, int[] prices) {
    int length = prices.length;
    if (length == 0) {
        return 0;
    }

    int[][] dp = new int[length][2 * k + 1];
    for (int i=1; i<=2*k-1; i+=2) {
        dp[0][i] = -prices[0];
    }
    for (int i=1; i<length; i++) {
        // 循环计算买入与卖出的最大金币
        for (int j=1; j<=2*k-1; j+=2) {
            dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1] - prices[i]);
            dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] + prices[i]);
        }
    }
    return dp[length-1][2 * k];
}

public int maxProfit(int[] prices) {
    int length = prices.length;
    int[][] dp = new int[length][4];
    dp[0][0] = -prices[0];
    for (int i=1; i<length; i++) {
        dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][3] - prices[i], dp[i-1][1] - prices[i]));
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][3]);
        dp[i][2] = dp[i-1][0] + prices[i];
        dp[i][3] = dp[i-1][2];
    }
    return Math.max(dp[length-1][1], Math.max(dp[length-1][2], dp[length-1][3]));
}

public int maxProfit(int[] prices, int fee) {
    int length = prices.length;
    int[][] dp = new int[length][2];
    dp[0][0] = -prices[0];
    for (int i=1; i<length; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i] - fee);
    }
    return dp[length-1][1];
}

public int maxProfit(int[] prices, int fee) {
    int result = 0;
    int minPrice = prices[0];

    for (int i=1; i<prices.length; i++) {
        // 当 minPrice是prices[i] - fee时，如果价格不比这个低，就没必要
        // 重新开启一次交易，因为会产生手续费，如果比这个低了，说明付了手续费
        // 也比持续收获利润的这种情况高
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else if (prices[i] > minPrice + fee) {
            result += prices[i] - minPrice - fee;
            // 防止重复计算手续费
            minPrice = prices[i] - fee;
        } 
    }
    return result;
}

1. dp[row][column] 到达该格子所获得的最大价值
2. dp[row][column] = max{左侧格子， 上侧格子} + grid[row][column]
3. dp[0][0] = grid[0][0]
4. 从左至右，从上至右
5. 举例

public int maxValue (int[][] grid) {
    if (grid.length==0 || grid[0].length==0) {
        return 0;
    }
    int rows = grid.length;
    int columns = grid[0].length;
    int[][] dp = new int[rows][columns];
    dp[0][0] = grid[0][0];
    for (int row=0; row<rows; row++) {
        for (int column=0; column<columns; column++) {
            if (row==0 && column==0) {
                continue;
            }
            // 注意处理越界情况，上侧格子只能可行越界，左侧格子只能可列越界
            int top = row-1<0 ? 0 : dp[row-1][column];
            int left = column-1<0 ? 0 : dp[row][column-1];
            dp[row][column] = Math.max(left, top) + grid[row][column];
        }
    }
    return dp[rows-1][columns-1];
}

private int maxLength;
public int lengthOfLongestSubstring (String s) {
    if (s.length() <= 1) {
        return s.length();
    }
    for (int left=0, right=1; right<s.length(); right++) {
        int index = this.indexOfRepeat(left, right, s);
        if (index == -1) {
            continue;
        } else {
            left = index + 1;
        }
    }
    return this.maxLength;
}

private int indexOfRepeat(int start, int target, String s) {
    int i;
    // 查找是否有重复的
    for (i=start; i<target; i++) {
        if (s.charAt(i) == s.charAt(target)) {
            break;
        }
    }
    // 记录最长的长度
    if (target + 1 - start > this.maxLength) {
        this.maxLength = target + 1 - start;
        // i < target 说明找到了重复的，不能包括长度不能包括当前字符
        if (i < target) {
            this.maxLength--;
        }
    }
    // 找到重复的, 返回重复的字符索引，否则返回-1
    if (i < target) {
        return i;
    } else {
        return -1;
    }
}

public int lengthOfLongestSubstring (String s) {
    // write code here
    if (s.length() <= 1) {
        return s.length();
    }
    int maxLength = 0;
    for (int left=0, right=1; right<s.length(); right++) {
        // 在[left, right)区间查找是否有重复字符
        int index = s.substring(left, right).indexOf(s.charAt(right));
        if (index != -1) {
            // 如果有重复字符，需要加上偏移量left，因为切割了字符串
            index += left;   
        }
        // 保存最长的长度
        if (maxLength < right + 1 - left) {
            maxLength = right + 1 - left;
            // 如果有重复的，长度不能包含当前字符，所以减一
            if (index != -1) {
                maxLength--;
            }
        }
        if (index != -1) {
            // 如果有重复的左指针指向重复的下一个
            left = index + 1;
        }
    }
    return maxLength;
}

public int lengthOfLongestSubstring (String s) {
    // write code here
    if (s.length() <= 1) {
        return s.length();
    }
    int maxLength = 0;
    Set<Character> set = new HashSet<>();
    set.add(s.charAt(0));
    for (int left=0, right=1; right<s.length(); right++) {
        char current = s.charAt(right);
        // 使用变量记录添加的结果，而不能每次都通过set.add()判断，因为第一次添加成功的话，再添加就会失败，因为set内容改变了
        boolean isRepeat = !set.add(current);
        // 计算当前的长度，包括了当前字符
        int currentLength = right + 1 - left;
        if (currentLength > maxLength) {
            maxLength = currentLength;
            // 如果当前是重复字符的话，还需减去当前字符
            if (isRepeat) {
                maxLength--;
            }
        }
        // 如果当前是重复字符的话，不停右移left
        if (isRepeat) {
            while (set.contains(current)) {
                // left++，最终会指向被移动的重复字符的右边
                set.remove(s.charAt(left++));
            }
            // set中重复的current已经被移除了，还需要加上current
            set.add(current);
        }
    }
    return maxLength;
}

public int lengthOfLongestSubstring (String s) {
    // write code here
    if (s.length() <= 1) {
        return s.length();
    }
    int maxLength = 1;
    int CHAR_NUMBER = 95;
    int length = s.length();
    // 记录字符上一次出现的索引，32～126(共95个)是字符：32是空格，
    // 其中48～57为0到9十个阿拉伯数字，65～90为26个大写英文字母，
    // 97～122号为26个小写英文字母，其余为一些标点符号、运算符号等。
    int[] previousIndex = new int[CHAR_NUMBER];
    // 索引初始化为-1
    for (int i=0; i<CHAR_NUMBER; i++) {
        previousIndex[i] = -1;
    }
    int[] dp = new int[length];
    // dp数组初始化
    dp[0] = 1;
    previousIndex[(int)s.charAt(0)-(int)' '] = 0;
    for (int i=1; i<length; i++) {
        int current = (int)s.charAt(i) - (int)' ';
        // 当前字符出现过
        if (previousIndex[current] == -1) {
            dp[i] = dp[i-1] + 1;
        } 
        // 当前字符未出现过 
        else { 
            int distance = i - previousIndex[current];
            // 距离小于等于dp[i-1]，说明在上一个字符串中有重复的，dp[i] = distance
            if (distance <= dp[i-1]) {
                dp[i] = distance;
            } 
            // 距离大于dp[i-1]，说明在上一个字符串中没重复的
            else { 
                dp[i] = dp[i-1] + 1;
            }
        }
        if (maxLength < dp[i]) {
            maxLength = dp[i];
        }
        previousIndex[current] = i;
    }
    return maxLength;
}

public int solve (String nums) {
    // write code here
    return dfs(nums.toCharArray(), 0);
}

private int dfs(char[] nums, int startIndex) {
    // 递归终止条件，判断到末尾，这种翻译可能成立
    if (startIndex == nums.length) {
        return 1;
    }
    // 有两种翻译方式，一种是翻译一个字符，一种是翻译两个字符
    // 翻译一个字符，不是'0'都可以翻译，是'0'返回0，表示该种翻译方式不可行
    int single;
    if (nums[startIndex] == '0') {
        return 0;
    } else {
        single = dfs(nums, startIndex+1);         
    }
    // 翻译两个字符，要求至少还剩两个字符，并且 当第一个字符是'1'的时候，肯定能两个字符一起翻译 
    // 当第一个字符是'2'的时候，第二字符小于等于'6'
    // 其他情况不能翻译，返回0
    int double_ = 0;   
    if ((startIndex<nums.length-1) && (nums[startIndex]=='1' || nums[startIndex]=='2' && nums[startIndex+1]<='6')) {
        double_ = dfs(nums, startIndex+2);
    }
    return single + double_;
}

public int solve (String nums) {
    // write code here
    int length = nums.length();
    if (length == 0) {
        return 0;
    }
    int[] dp = new int[length];
    dp[0] = nums.charAt(0)=='0' ? 0 : 1;
    for (int i=1; i<length; i++) {
        int single = 0;
        int double_ = 0;
        char previous = nums.charAt(i-1); 
        char current = nums.charAt(i);
        if (current != '0') {
            single = dp[i-1];
        }
        if (previous=='1' || previous=='2' && current <= '6') {
            if (i == 1) {
                double_ = 1;
            } else {
                double_ = dp[i-2];
            }
        }
        dp[i] = single + double_;
    }
    System.out.println(Arrays.toString(dp));
    return dp[length-1];
}

/*
    1. 确定下标含义
    dp[i] 以nums[i] 结尾的，前面递增子序列的最长长度
    2. 递推公式
    位置的最长升序子序列，等于之前的最长升序子序列最大值+1
    for j in range(0, i):
        if (nums[i] > nums[j]):
            max_value = max(dp[j], max_value)
        dp[i] = max_value+1
    3. 初始化
    各个位置，至少长度为1，都初始化为1
    4. 从前向后遍历
    5. 举例[10,9,2,5,3,7,101,18]
    1 1 1 2 2 3 4 4
*/
public int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length];
    for (int i=0; i<dp.length; i++) {
        dp[i] = 1;
    }
    int result = 1;
    for (int i=1; i<dp.length; i++) {
        for (int j=0; j<i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j]+1);
            }
        }
        result = Math.max(dp[i], result);
    }
    return result;
    
}

  1 dp[i][d] 包括i的之前的数组公差为d的子序列长度
  2. dp[i][d1] = dp[i-1][d1] + 1
     dp[i][d2] = dp[i-2][d2] + 1
  3. dp[0][*] = 1
  4. 前后顺序
  5.      [9,   4,   7,   2,   10]
dp[i][-5]  1    2         2
dp[i][3]   1         2         3
dp[i][-2]            2    2
dp[i][-7]                 2
dp[i][8]                       2
dp[i][6]                       2
dp[i][1]                       2

public int longestArithSeqLength(int[] nums) {
    int length = nums.length;
    if (length <= 2) {
        return length;
    }
    Map<Integer, Integer> dp[] = new Map[length];
    for (int i=0; i<length; i++) {
        dp[i] = new HashMap<>();
    }
    int result = 0;
    for (int i=1; i<length; i++) {
        for (int j=0; j<i; j++) {
            int distance = nums[i] - nums[j];
            dp[i].put(distance, dp[j].getOrDefault(distance, 1) + 1);
        }
        for (Integer item : dp[i].values()) {
            result = Math.max(result, item);
        }
    }
    return result;
}

public int longestSeqLength(int[] nums) {
    int length = nums.length;
    if (length <= 2) {
        return length;
    }
    Map<Double, Integer> dp[] = new Map[length];
    for (int i=0; i<length; i++) {
        dp[i] = new HashMap<>();
    }
    int result = 0;
    for (int i=1; i<length; i++) {
        for (int j=0; j<i; j++) {
            double ratio = (double)nums[i] / nums[j];
            dp[i].put(ratio, dp[j].getOrDefault(ratio, 1) + 1);
        }
        for (Integer item : dp[i].values()) {
            result = Math.max(result, item);
        }
    }
    return result;
}