虽然是叫动态规化,但第一个并不是动态规化的东西,先从一个树开使。

LeetCode 124 Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

有一说一，这题的分类是困难，这让我对困难题一下没有这么恐惧了。

题目的大概意思是让从一颗树中找到权值最大的路径，一个后序遍历就可以做完，不过还是有几点要注意的。

#include <iostream>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

// @leet start
class Solution {
public:
  int ans = -1000;
  int maxgain(TreeNode *root) {
    if (root == nullptr) {
      return 0;
    }
    int right = max(0, maxgain(root->right));
    int left = max(0, maxgain(root->left));
    ans = max(ans, left + right + root->val);
    return max(left, right) + root->val;
  }
  int maxPathSum(TreeNode *root) {
    maxgain(root);
    return ans;
  }
};

注意点一：

当子树的权值小于 0 时，应该直接放弃，也就是代码中的

    int right = max(0, maxgain(root->right));

注意点二： 当自己做为子树的时候，只能选一边做为新路径的一部份

    return max(left, right) + root->val;

这也应该是能想到的，但我还是卡了一会，没想通为什么和 ans 算的不一样。

300. Longest Increasing Subsequence

动态规化的开始，最长递增子序列

题目几年前的时候我都没看懂，现在才发现说的是子序列，而我理解的一直是子串。

笔记

子序列是可以不连续，而子串的要求是连续。

动态规化的难点有三

难点一：问题的状态划分

思想和数学归纳法很像，找到子问题，子问题都成立的情况下，自己要怎么成立。

本题的子问题则可以定义为以自己结尾的子序列最长的长度是多少。

那么就很容易想到是之前最长的+1.便是自己的，代码就很简单了。

补充

后面还加了一个二分法的例子，不过没有证明，等后面全部看完了再看看吧

题号 354. Russian Doll Envelopes 强制用这种方法，

1143. Longest Common Subsequence

还有一个是题号 53 maximum subarray 但是比较简单

最长公共子序列,比较好处理的有俩个边界.

当是 0 的时候,dp 自然是 0

当 str1[i]==str[j] 的时候,dp[j][i]=dp[j-1][i-1]

主要的问题是当不相等的时候, 为什么是 dp[j-1][i],dp[j][i-1]

需要理解俩点

1. dp是递增的,长的最长公共子序列, 一定是比短的要长的（最少是相等）
2. 当i,j不相等是，值便是 i-1,j j-1,i ,i-1,j-1 三者中的最大值,但i-1,j-1,永远不会是最大值，所以比较前俩者就好了。

72. Edit Distance

有一说一,这个理解比上面的要难,不过最难的还是dp数组的定义，这里的定义是 s[0...i],s[0....j] 的最小编辑距离

让我疑惑的主要有俩点，一个是为什么dptable的遍历顺序是反的，一个是为什么迭代是正的

其实想通了也不是很难，子问题划分，对于不同的 i, j，来进行解答， 大的不影响小的，大的答案依靠小的。

dptable的思路就是递归不断的向下找，迭代就是从小的一点一点解出大的，这是我最习惯的。