FrankChan

题解

/ 注册

全部文章 / 题解（共3篇）

排成一条线的纸牌博弈问题

#include <vector> #include <iostream> using namespace std; int win1(vector<int>& arr) {//使用标准...

动态规划

2020-04-23

0 1003

丢棋子问题最优解

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

动态规划

2020-04-22

1 1474

最长公共子串问题空间复杂度为O(1)的解法

图是从左神的书里截的。这个思路很很巧妙。例如当前有如下两个串：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++...

动态规划

2020-04-21

7 1116