Re: [閒聊] 每日leetcode
※ 引述 《dont (dont)》 之銘言：
:
: 1937. Maximum Number of Points with Cost
:
: ## 思路
:
: 直接照題目暴力作DP的話 會TLE -- O(MN^2)
:
題目:
有一個二維陣列
你要從每一排拿一個元素
然後要減掉他們index的距離
就是往下掉拿數字的意思
不過可以選任何地方掉 代價是扣掉距離
思路:
暴力會超時
這題暴力會超時的原因是
m*n*n會超久 主要是那個n平方在搞
然後如果直接看下一步去哪裡的全部選擇的話
就是n平方
所以主要就要想去哪裡的選擇的方法 怎麼改
我覺得他每日出的還不錯
這就是昨天那個找前面的最大值
套用在這邊
說的意思就是不用找全部可能
只要找上面的
左邊最大可能 右邊最大可能 跟正上比就好
然後dp下來
姆咪姆咪
```cpp
class Solution {
public:
long long maxPoints(vector<vector<int>>& points)
{
int n = points[0].size();
int m = points.size();
vector<vector<long long>> paper(m,vector<long long>(n));
for(int i = 0 ; i < m ; i ++)
{
for(int j = 0 ; j < n ; j ++)
{
paper[i][j] = (long long)points[i][j];
}
}
long long res =0;
for(int i = 1 ; i < m ; i ++)
{
long long pre = 0;
for(int j = 0 ; j < n ; j ++)
{
pre--;
paper[i][j] = max(max(paper[i-1][j] + points[i][j],pre + points[
i][j]),paper[i][j]);
pre = max(paper[i-1][j] , pre);
}
pre = 0;
for(int j = n-1 ; j >= 0 ; j --)
{
pre--;
paper[i][j] = max(max(paper[i-1][j] + points[i][j],pre + points[
i][j]),paper[i][j]);
pre = max(paper[i-1][j] , pre);
}
}
for(int i = 0 ; i < n ; i ++)
{
res = max(res ,paper[m-1][i]);
}
// for(int i = 0 ; i < m ; i ++)
// {
// for(int j = 0 ; j < n ; j ++)
// {
// cout<<paper[i][j]<<" ";
// }
// cout<<endl;
// }
// cout<<endl;
return res;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.41.248 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723877614.A.9F9.html
→
08/17 14:53,
1年前
, 1F
08/17 14:53, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 728 之 1548 篇)：