动态规划29：673. 最长递增子序列的个数

动态规划解题步骤：

1.确定状态表示：dp[i]是什么

2.确定状态转移方程：dp[i]等于什么

3.初始化：确保状态转移方程不越界

4.确定填表顺序：根据状态转移方程即可确定填表顺序

5.确定返回值

题目链接：673. 最长递增子序列的个数 - 力扣（LeetCode）

题解：

1.状态表示： len[i]表示以nums[i]结尾的最长递增子序列的长度

                      count[i]表示以nums[i]结尾的最长递增子序列个数

2.状态转移方程：见代码分析

3.初始化：len表和count表的最低值为1，所以在创建表时就将其全部初始化为1

4.填表顺序：从左向右依次填写

5.返回值：一次循环，遍历len表，如果当前len值大于已确定的最大长度，更新最大长度并记录返回值ans为count[i]；如果当前len值等于已确定的最大长度，返回值ans+=count[i]；否则无需更新

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        //len[i]表示以nums[i]结尾的最长递增子序列的长度
        //如果存在nums[i]>nums[j] len[i]=max(len[i],len[j]+1)
        //如果不存在，len[i]=1
        //count[i]表示以nums[i]结尾的最长递增子序列个数
        //如果存在nums[i]>nums[j]并且len[j]+1>len[i] count[i]=count[j]
        //如果存在nums[i]>nums[j]并且len[j]+1=len[i] count[i]+=count[j]
        //如果存在nums[i]>nums[j]并且len[j]+1<len[i] 无需更新count[i]
        //如果不存在，count[i]=1
        size_t n=nums.size();
        //创建dp表
        vector<int> len(n,1),count(n,1);
        //初始化
        //len表和count表的最低值为1，所以创建表时就初始化
        //填表
        int ans=0,max=0;//max为最长递增子序列的长度
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<i;++j)
            {
                if(nums[i]>nums[j])
                {
                    //更新count表
                    if(len[j]+1>len[i])
                    {
                        len[i]=len[j]+1;//更新len表
                        count[i]=count[j];//更新count表
                    }
                    else if(len[j]+1==len[i])
                    {
                        count[i]+=count[j];//更新count表
                    }               
                }
            }
            //返回值
            if(len[i]>max)
            {
                max=len[i];
                ans=count[i];
            }
            else if(len[i]==max)
            {
                ans+=count[i];
            }
        }
        //返回值
        return ans;
    }
};