139

这道题是完全背包类问题，可以把字符串当作背包，字典当作物品，同时本题求解的是排列数。dp[i]表示字符串数量为i的背包能否在字典中找到对应的字符，能就是true，否则就是false。递推关系是如果前一个dp返回的是true，而且当前字符能在字典中找到，那么当前dp就是true。

300

这道题的dp[i]表示以nums[i]为结尾的递增子序列的最长长度是dp[i]，递推关系是if(dp[i]>dp[j]) dp[i]=max(dp[i],dp[j]+1)，由这个递推关系就能得到遍历顺序了。

class Solution {

public:

    int lengthOfLIS(vector<int>& nums) {

        int n=nums.size();

        vector<int> dp(n,1);

        int ans=1;

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

        {

            for(int j=0;j<=i;j++)

            {

              if(nums[i]>nums[j]) dp[i]=max(dp[j]+1,dp[i]);

            }

            if(dp[i]>ans) ans=dp[i];

        }

        return ans;

    }

};

152

这道题的思路是因为不知道元素的正负号，最小的负值和最大的正值都有可能称为乘积最大的值，所以这里维护两个值dpmin和dpmax，dpmin保存每次遍历的最小值，dpmax保存每次遍历的最大值。定义t_max和t_min,t_max用于计算dpmax与当前值的积，t_min用于计算当前值与dpmin的积。同样是因为当前值可正可负，所以递推关系是： dpmax=max(max(t_max,t_min),nums[i]); dpmin=min(min(t_min,t_max),nums[i])。