动态规划-算法题-整理

8、打家劫舍-环，挨着不能同时偷

leetcode 213 环其实就是说明第一个0和最后一个n-1不能同时偷，那么其实就相当于 max(偷0-n-2/偷1-n-1).调用两边上一题的代码，上一题可以优化，因为只与上一个和上上个有关，所以只需要保存pre/now

int dp_8_7(vector nums,int s,int e){int pre=nums[s],now=max(nums[s],nums[s+1]);for(int i=s+2;i<=e;i++){   int temp=now;now=max(now,pre+nums[i]);pre=temp;}return now;
}int dp_8(){vector nums;int n;while(cin>>n) nums.push_back(n);if(nums.size()==0) return 0;if(nums.size()==1) return nums[0];if(nums.size()==2) return max(nums[0],nums[1]);if(nums.size()==3) return max(nums[0],max(nums[1],nums[2]));else return max(dp_8_7(nums,0,nums.size()-2),dp_8_7(nums,1,nums.size()-1));return 0;
}

8、打家劫舍-树，挨着的层不能同时偷

leetcode 337 二叉树，一定要隔层偷。
相同的思想，记录下一层的最大和/下下层的最大和。但是下面层分不同的支路。res(2)表示当前下一层和对应的下下层的和。
因此return res-> res[0](上一层的下层，所以是用了当前root的,那么就一定用隔层的)= resl[1]+resr[1]+val
res[1]=(没用当前这个，可能用的下/下下层中大的那个)=max(resl[0],resl[1])+max(resr[0],resr[1])

class Solution:def hh1(self,root):#返回的值是用当前这一层的最大值和使用当前这一层的下一层的最大值res = [0, 0]if root==None: return resres1=self.hh1(root.left)res2=self.hh1(root.right)#不使用当前点的最大值,其实是！！4种情况1/2 -》1子节点/2的子节点一共4个点，父子节点不能同时使用，所以，其实就是分别找最大值加起来就是不使用当前根结点的最大值！res[1]=max(res2[0],res2[1])+max(res1[0],res1[1])res[0]=res1[1]+res2[1]+root.valreturn resdef rob(self, root: TreeNode) -> int:#其实还是或者是要跟+跟的孙子/只要跟的儿子，所以其实留2层就ok了if root==None: return 0return max(self.hh1(root))

2、银行等问题

1、堆金币问题

https://www.nowcoder.com/questionTerminal/6d3ccbc5b6ad4f12b8fe4c97eaf969e0?orderByHotValue=1&page=1&onlyReference=false

有 N 堆金币排成一排，第 i 堆中有 C[i] 块金币。每次合并都会将相邻的两堆金币合并为一堆，成本为这两堆金币块数之和。经过N-1次合并，最终将所有金币合并为一堆。请找出将金币合并为一堆的最低成本。

其中，1 <= N <= 30，1 <= C[i] <= 100

因为说了只能相邻的合并，因此可以看成dp[i][j]：从0号金币到j号金币合为一堆的最低成本。

每次合并都是两个两个合并,因此可以先看，两个合并的最低成本，[0,1] [1,2]这样，

之后看三个合并的最低成本，其实就是[0,1]+2 / 0+[1,2]

看[i][i+len]这个区间和为一个堆，要花费多少，那么其实可以分为2个区间，[i][j]+[j][i+len]+这次就是sum[i,i+len]

#include
#include
#include 
using namespace std;int vec_sum(vector h,int b,int e){int ans=0;for(int i=b;i<=e;i++)ans+=h[i];return ans;
}int main(){int num,ans=0,len=1;cin>>num;vector jinbi(num,0);vector > he;for(int i=0;i jinbii(num,0x7ffffff);he.push_back(jinbii);}for(int i=0;i>jinbi[i];he[i][i]=0;}while(len

#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 16
#define MOD 10007
#define E 1e-6
#define LL long longint nn;
int a[21][21];
int dp[21][1<>i)&1)//看state从右往左的第i位是不是1，是1说明要a的第k行的从右往做的第i个，也就是从左往右第nn-1-i个res+=a[k][nn-1-i];return res;
}
int dp_9_1()
{while(scanf("%d",&nn)!=EOF){for(int i=0;i>1)))//判断本行状态，要求横向不冲突，每一行其实是一样的要求sta[len++]=i;for(int i=0;i

http://acm.hdu.edu.cn/showproblem.php?pid=1429

//并不是所有的都可以走回头路！只有添加了新钥匙才能走回路！所以也就是说visited不再是1维了，而应该是三维度，
// 第3个维度应该表示的是a-j有没有拿到，正常考虑用vector(10)表示有么有拿到，但是这样visited就不是3维度了，是12维度了。
// 因此让1111111111这个数表示有没有拿到这个钥匙,也就是2^10=1024，拿到钥匙和才能走回头路！
// 我自己之前的做法是，queue保留当前点+钥匙状态，每一个点都可以走回头路，不可以
//第3维度也不可以是10，这样不能用一个点来表示状态，需要用10个点来表示状态。那么这个visited就不能表示当前这个状态有没有遍历过了。遍历到这个点其实可能有2^10状态
//0-1111111111 分别代表一个状态，

const int MAX=25;
struct point
{int x,y,step,state;point(int x=0,int y=0,int step=0,int state=0):x(x),y(y),step(step),state(state){};
};
char g[MAX][MAX];
int vis[MAX][MAX][1025];
int dirx[4]={0,1,0,-1};
int diry[4]={1,0,-1,0};
int n,m,t;
int sx,sy,ex,ey;
bool judgein(int x,int y)
{return 0<=x&&x que;vis[sx][sy][0]=1;que.push(point(sx,sy,0,0));while(!que.empty()){point top=que.front();que.pop();int x=top.x;int y=top.y;int step=top.step;int state=top.state;if(step>=t){return -1;}if(x==ex&&y==ey){return step;}for(int i=0;i<4;i++){int nx=x+dirx[i];int ny=y+diry[i];int nstep=step+1;int nstate=state;if(judgein(nx,ny)&&g[nx][ny]!='*'&&!vis[nx][ny][nstate]){if(g[nx][ny]=='.'){vis[nx][ny][nstate]=1;que.push(point(nx,ny,nstep,nstate));}else if(g[nx][ny]>='A'&&g[nx][ny]<='J'){int key=nstate&(1<<(g[nx][ny]-'A'));if(key){vis[nx][ny][nstate]=1;que.push(point(nx,ny,nstep,nstate));}}else if(g[nx][ny]>='a'&&g[nx][ny]<='j'){nstate=nstate|(1<<(g[nx][ny]-'a'));vis[nx][ny][nstate]=1;que.push(point(nx,ny,nstep,nstate));}}}}return -1;
}
int main_ok()
{while(scanf("%d%d%d",&n,&m,&t)!=EOF){getchar();for(int i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！