#include <vector> #include <iostream> using namespace std; int win1(vector<int>& arr) {//使用标准二维dp     int n = arr.size();     vector<vector<int>> first(n, vector<i...

这道题需要转换思路才能把时间复杂度降到O( ) 以下。基本思路是目前有i个棋子，如果扔j次最多能解决的楼层数。构造二维dp，dp[i][j]表示i颗棋子，扔j次最多能解决的楼层数。 假设第1个棋子扔在a层楼是最优的尝试。 1.如果第1个棋子已碎，那就向下，看i-1个棋子扔j-1次最多搞定多少层楼。对应dp[i-1][j-1] 2.如果第1个棋子没碎，那就向上，看i-1个棋子扔j次最多搞定多少层楼。对应dp[i-1][j] 3.a层楼本身也是被搞定的1层。 +1即有：dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + 1 #include <v...

图是从左神的书里截的。这个思路很很巧妙。例如当前有如下两个串：a b c d eb e b c d构造图4-10，图中的数值表就是二维dp[i][j]的值。dp[i][j]只与dp[i-1][j-1]有关。每一轮斜线扫描时，开始长度curLen = 0，如果对应i, j的字符相等，则curLen++，不同则又将curLen重置为0。相当于用curLen来代替dp[i][j]，省下了O(m*n)的空间。 #include <string> #include <iostream> using namespace std; string commonStr(string&am...

#给牛客的问题反馈和建议#