最长单调递增子序列问题和数字三角形问题的动态规划算法实现和效率分析

最长单调递增子序列问题的动态规划算法实现：

1. 定义状态：dp[i]表示以第i个元素为结尾的最长单调递增子序列的长度。

2. 初始化：dp[i]初始值为1，因为任意一个元素本身就是一个长度为1的单调递增子序列。

3. 状态转移方程：对于每个元素i，枚举其之前的元素j（j<i），如果nums[j] < nums[i]，则dp[i] = max(dp[i], dp[j]+1)。

4. 最终结果：遍历dp数组，找到最大值。

代码实现：

def longestIncreasingSubsequence(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)

数字三角形问题的动态规划算法实现：

1. 定义状态：dp[i][j]表示从顶部走到(i,j)位置的最小路径和。

2. 初始化：dp[0][0] = triangle[0][0]，其他dp[i][j]的初始值为正无穷。

3. 状态转移方程：对于每个位置(i,j)，有两个状态可以转移过来，即(i-1,j)和(i-1,j-1)，因此dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]。

4. 最终结果：遍历dp数组的最后一行，找到最小值。

代码实现：

def minimumTotal(triangle):
    n = len(triangle)
    dp = [[float('inf')] * n for _ in range(n)]
    dp[0][0] = triangle[0][0]
    for i in range(1, n):
        for j in range(i+1):
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
    return min(dp[-1])

效率分析：

最长单调递增子序列问题的时间复杂度为O(n^2)，空间复杂度为O(n)。

数字三角形问题的时间复杂度为O(n^2)，空间复杂度为O(n^2)。