趣味SQL题：力扣213. 打家劫舍 II

newkid

分析：当打劫第k家时，k-1肯定不能抢，所以含K的收益V(K)是k-2和k-3的最大金额加上k本身的现金额。k-4就没必要考虑因为肯定比k-2小。用递归sql把第k-1,k-2,k-3的打劫情况存储起来供下次递归挑选。
起点分两种情况，选择第一家或者第二家，如果第一家抢过了最后一家就不能抢。
假设总共N家，最终答案就是在v(N),v(N-1),v(N-2)里面选择。

with
house as (
select rownum as id,column_value as cash
  from TABLE(sys.odcinumberlist(118,871,258,694,451,792,117,515,471,445,576,126,403,644,663,504,921,947,704,710,948,27,505,721,980,837,408,939,939,810,662,616,685,758,312,779,911,635,429,62,682,572,81,111,974,700,730,868,548,304,600,678,479,951,348,614,147,971,337,331,9,904,893,542,803,439,291,673,149,289,773,644,554,619,687,621,738,897,501,265,234,511,549,250,722,271,404,365,715,668,205,712,106,946,128,472,960,122,332,957))
)
,t(start_id,id,val,path,val2,path2,val3,path3) as (
select id,id,cash,cast(id||'' as varchar2(4000)),0,cast('' as varchar2(4000)),0,cast('' as varchar2(4000))
  from house
where id in (1,2)
union all
select t.start_id,house.id
      ,greatest(t.val2,t.val3)+house.cash
      ,case when t.val2>t.val3 then t.path2 else t.path3 end||','||house.id
      ,t.val
      ,t.path
      ,t.val2
      ,t.path2
  from t
      ,house
where t.id+1=house.id   
)
select val,path
from t,(select max(id) as cnt from house)
where id in (cnt-1,cnt-2) or id=cnt and start_id=2
order by val desc
fetch first 1 row with ties;

VAL     PATH
---------------------------------------------
31752        2,4,6,8,11,13,15,17,19,21,24,26,28,30,32,34,36,38,41,43,45,47,49,52,54,56,58,60,62,64,66,68,71,73,75,77,79,81,83,85,87,89,92,94,97,100

Elapsed: 00:00:00.26

〇〇

当少于等于3间的时候，选最大的1间

〇〇

〇〇 发表于 2024-9-24 06:17
当少于等于3间的时候，选最大的1间

你的结果是对的
with recursive house(id,cash)
as
(select 1,1 union all
select 2,3 union all
select 3,5
),
t(start_id,id,val,path,val2,path2,val3,path3) as (
select id,id,cash,cast(id||'' as varchar(4000)),0,cast('' as varchar(4000)),0,cast('' as varchar(4000))
  from house
where id in (1,2)
union all
select t.start_id,house.id
      ,greatest(t.val2,t.val3)+house.cash
      ,case when t.val2>t.val3 then t.path2 else t.path3 end||','||house.id
      ,t.val
      ,t.path
      ,t.val2
      ,t.path2
  from t
      ,house
where t.id+1=house.id   
)
select val,path
from t,(select max(id) as cnt from house)
where id in (cnt-1,cnt-2) or id=cnt and start_id=2
order by val desc
limit 1;

┌───────┬─────────┐
│  val  │  path   │
│ int32 │ varchar │
├───────┼─────────┤
│     5 │ ,3      │
└───────┴─────────┘