java笔试动态规划算法

动态规划是一种算法思想，常用于求解最优化问题。它的主要思想是将原问题分解为若干个子问题，并且每个子问题只需求解一次，将其结果保存下来，避免重复计算，从而达到减少计算量的目的。

在Java笔试中，动态规划常用于解决最长公共子序列、最小编辑距离、背包问题等。例如，对于最长公共子序列问题，可以使用动态规划算法求解，具体步骤如下：
1. 定义状态：使用二维数组dp[i][j]表示字符串s1的前i个字符和字符串s2的前j个字符的最长公共子序列长度。
2. 状态转移方程：如果s1[i-1]等于s2[j-1]，则dp[i][j]=dp[i-1][j-1]+1，否则dp[i][j]=max(dp[i-1][j],dp[i][j-1])。
3. 初始化状态：dp[j]=0和dp[i]=0，其中0<=i<=m,0<=j<=n，其中m为字符串s1的长度，n为字符串s2的长度。
4. 求解最终结果：dp[m][n]即为字符串s1和s2的最长公共子序列长度。