首页 > 代码库 > 算法练习--- DP 求解最长上升子序列（LIS）
算法练习--- DP 求解最长上升子序列（LIS）
问题描写叙述：
1. 找出DP公式：
dp[i] = dp[j] + 1 (j<i && a[j]<a[i] && dp[i] < dp[j]+1)
2.实现代码
dpArr[0...n-1]中，最大的元素即为所求。
对于2,5,3,1,9,4,6,8,7，找出最长上升子序列的个数
最长上升子序列定义：
对于i<j i,j∈a[0...n] 满足a[i]<a[j]
1. 找出DP公式：
dp[i] = dp[j] + 1 (j<i && a[j]<a[i] && dp[i] < dp[j]+1)
2.实现代码
void Main()
{
DP_LIS();
Console.WriteLine(dpArr);
}
static int[] arr = new int[9]{2,5,3,1,9,4,6,8,7};
static int n = 9;
static int[] dpArr = new int[9];
static void DP_LIS(){
for(var i= 0;i < n; i++){
dpArr[i] = 1;
for(var j = 0;j < i; j++){
if(arr[j]<arr[i] && dpArr[i] < dpArr[j] + 1){
dpArr[i] = dpArr[j]+1;
}
}
}
}
dpArr[0...n-1]中，最大的元素即为所求。
作为联系，本例打印出了dp数组中的全部元素
算法练习--- DP 求解最长上升子序列（LIS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。