dp算法篇Day8

**DP算法篇 Day8**

在前面的几天里，我们已经学习了DP算法的基本概念、动态规划表格的建立以及如何使用DP解决一些经典的问题。今天，我们将继续深入探讨DP算法的应用，特别是关于背包问题和最长上升子序列问题。

**1. 背包问题**

背包问题是一种经典的DP问题，它涉及到在一个背包中放入尽可能多的物品，而这些物品的重量和价值都有所限制。我们可以将其视为一种0-1背包问题，即每个物品只能被放入一次。

**背包问题的数学描述**

假设我们有 n 个物品，每个物品的重量为 w_i 和价值为 v_i。我们希望在一个容量为 W 的背包中放入尽可能多的物品，使得总价值最大化。

**DP算法解决背包问题**

为了解决这个问题，我们可以使用以下DP表格：

| |0 |1 |2 | ... | n |
| --- | --- | --- | --- | ... | --- |
|0 |0 |0 |0 | ... |0 |
|1 |0 | v_1 | | ... | |
|2 |0 | | v_1 + v_2 | ... | |
| ... | ... | ... | ... | ... | ... |
| n |0 | | | ... | max(v_1, v_2, ..., v_n) |

其中，dp[i][j] 表示在前 i 个物品中放入重量为 j 的背包的最大价值。

**代码实现**

def knapsack(W, wt, val, n):
 K = [[0 for w in range(W +1)] for i in range(n +1)]

 # Build table K[][] in bottom up manner for i in range(n +1):
 for w in range(W +1):
 if i ==0 or w ==0:
 K[i][w] =0 elif wt[i -1] <= w:
 K[i][w] = max(val[i -1] + K[i -1][w - wt[i -1]], K[i -1][w])
 else:
 K[i][w] = K[i -1][w]

 return K[n][W]


# Driver codeval = [60,100,120]
wt = [10,20,30]
W =50n = len(val)

print(knapsack(W, wt, val, n))

**2. 最长上升子序列问题**

最长上升子序列问题是一种经典的DP问题，它涉及到在一个给定的序列中找到一个长度最大的上升子序列。

**最长上升子序列问题的数学描述**

假设我们有一个长度为 n 的序列，序列中的每个元素都有一个值。我们希望找到一个长度最大的上升子序列，使得该子序列中每两个连续元素的值都大于前一个元素。

**DP算法解决最长上升子序列问题**

为了解决这个问题，我们可以使用以下DP表格：

| |0 |1 |2 | ... | n |
| --- | --- | --- | --- | ... | --- |
|0 |0 |0 |0 | ... |0 |
|1 |0 |1 | | ... | |
|2 |0 | |2 | ... | |
| ... | ... | ... | ... | ... | ... |

其中，dp[i] 表示序列中前 i 个元素的最长上升子序列长度。

**代码实现**

def longest_ascending_sequence(arr):
 n = len(arr)
 dp = [1] * n for i in range(1, n):
 for j in range(i):
 if arr[i] > arr[j]:
 dp[i] = max(dp[i], dp[j] +1)

 return max(dp)


# Driver codearr = [10,22,9,33,21,50,41,60]
print(longest_ascending_sequence(arr))

以上就是今天关于DP算法的内容。我们学习了背包问题和最长上升子序列问题的解决方法，以及如何使用DP表格来求解这些问题。希望通过这些例子，你能够更好地理解DP算法的基本概念和应用。