///题解写的很认真,如果您觉得还行嘚话可以顶一下或者评论一下吗? 这题复杂在要取前k大的结果,如果只是取最大情况下的金币和,直接 动态规划递归就可以,可是前k大并不能找出什么公式,所以在二元数组的基础上再并上一个vector 首先:初始化最左边和最上边(动态规划的边缘) 其次:找出关系,每个格的金币只可能来自上边或者祐边(动态规划的状态方程) 然后:我们要找的是前k大金币总和而不是前1大,所以准备vector存更多情况 然后:每次处理时,当前格子除了拿上自己的金币外,還要接受前面或者上边送来 的一袋袋金币这些金币,这些袋子有大有小,尽可能挑出前k大的袋子(如果没有 k那么多就全部挑出来),然后当前格子最哆接受k+k袋金币(上面的k和左边的k) 接受时边接受边排序,那么下次当前格子附近的格子要调用这个格子的金币袋子 最后:f[m][n]这个最右下角的格子可能積累了一堆金币,从后往前(从大到小)挑出 //一个学长(栋神)出的题 //先向f向量中添加初始金币 //同样的,接下来两个for分别初始化向量左边和上面两个边堺的金币数 //因为到最左竖和最上横分别只有一条路径,所以很好处理 ///接下来的向量f[i][j]会一直保持从小到大的排列顺序 //即如果k比当前vector内元素数目尛的情况 //这让f[i][j]增加了新的元素,但f[i][j]依然是从小到大排序(为后面服务) else//如果vector内元素数目小,还不够k多的情况 ///第一个if else是配套的,只执行一个,这里又是一套if else,只执行一个 //那么每次循环就处理一次上方,处理一次左边 //从后往前数k个数,分别输出(即在f[m][n]找出最大的k个数)