UC知道如何编“最长上升子序列”？（（pascal）要递归）
来源：百度知道 编辑：UC知道 时间：2024/05/28 11:54:05
var
i,n:integer;
a,f:array[1..1000]of integer;
function maxlen(k:integer):integer;
forward;
function max(k:integer):integer;
var m:integer;f:boolean;
begin
m:=1;
for i:=1 to k-1 do
if (a[k]>a[i])and(maxlen(i)>=m )
then begin m:=maxlen(i); end;
for i:=1 to k-1 do
if (a[k]>a[i])
then begin f:=false;break; end;
if f
then max:=0
else max:=m;
end;
function maxlen(k:integer):integer;
begin
if f[k]<>0
then maxlen:=f[k]
else
if k=1
then maxlen:=1
else
begin
f[k]:=max(k)+1;
maxlen:=f[k];
end;
end;
begin
read(n);
for i:=1 to n do
read(a[i]);
f[1]:=1;
writeln(maxlen(n));
end.
i,n:integer;
a,f:array[1..1000]of integer;
function maxlen(k:integer):integer;
forward;
function max(k:integer):integer;
var m:integer;f:boolean;
begin
m:=1;
for i:=1 to k-1 do
if (a[k]>a[i])and(maxlen(i)>=m )
then begin m:=maxlen(i); end;
for i:=1 to k-1 do
if (a[k]>a[i])
then begin f:=false;break; end;
if f
then max:=0
else max:=m;
end;
function maxlen(k:integer):integer;
begin
if f[k]<>0
then maxlen:=f[k]
else
if k=1
then maxlen:=1
else
begin
f[k]:=max(k)+1;
maxlen:=f[k];
end;
end;
begin
read(n);
for i:=1 to n do
read(a[i]);
f[1]:=1;
writeln(maxlen(n));
end.
var
i,j,k,m,n:longint;
a:array[1..1000] of longint;
f:array[1..1000] of longint;
begin
readln(n);
for i:= 1 to n do
read(a[i]);
for i:= 1 to n do
begin
m:=0;
for j:= 1 to i-1 do
if (a[i]>a[j]) and (f[j]>m) then m:=f[j];
f[i]:=m+1;
end;
m:=0;
for i:= 1 to n do
if f[i]>m then m:=f[i];
writeln(m);
end.
你的看不大懂，是记忆化搜索吗？
这个题是标准的动态规划，不要复杂化了
动态规划解法
f[1]:=1;
max:=f[1];
for i:=2 to n do
begin
for j:=1 to i-1 do
if (a[j]<a[i])and(f[j]>f[i]) then f[i]:=f[j];(找最大的f[j]);
f[i]:=f[i]+1;(如果前面没有比a[i]大的则f[i]=1否则为f[i]+1);
end;
writeln(max);
end.