题目

我们正在玩一个猜数游戏，游戏规则如下：

我从 **1 **到 n 之间选择一个数字，你来猜我选了哪个数字。

每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。

然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。

示例:

n = 10, 我选择了8.

第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。

游戏结束。8 就是我选的数字。

你最终要支付 5 + 7 + 9 = 21 块钱。

给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏

思路

刚开始没看明白，看了解析才知道。
设置数组dp，其中dp[i][j]表示从i到j所需拥有多仨后现金才能保证赢得这个游戏。
因此最后返回dp[1][n]即可。

对于dp[i][j]，其值应该为：每次猜测结果为x的时候，dp[i][x-1]与dp[x+1][j]中的最大值与猜测的x相加，这样才能保证但在dp[i][j]内所有的猜测组合都可以在某个现金之内完成。
从n->0开始遍历i，对于每个i，从i-n遍历j，对于里面的所有j，选择预测为x的时候，选择dp[i][x-1]与dp[x+1][j]中的最大值与其相加相加即可。
对于

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int getMoneyAmount(int n) {
        int dp[n+2][n+2];
        memset(dp,0,sizeof(int)*(n+2)*(n+2));
        for(int i=n;i>=1;--i){
            for(int j = i;j <= n;++j){
                if(i==j) dp[i][j] = 0;
                else{
                    dp[i][j] = INT_MAX;
                    for(int x=i;x<=j;++x){
                        dp[i][j] = min(dp[i][j],max(dp[i][x-1],dp[x+1][j])+x);
                    }
                }
            }
        }
        return dp[1][n];
    }
};

题目

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 **连续的1 **的个数。

示例 1:

输入: 5
输出: 5
解释:
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

说明: 1 <= n <= 109

思路

说实话没怎么懂，看 @宫水三叶 的讲解，抄了抄代码。
@宫水三叶的 讲解

这是一道典型的「数位 DP」题。

对于「数位 DP」题，都存在「询问 [ a , b ] [a, b] [a,b]（ a a a 和 b b b 均为正整数，且 a < b a < b a<b）区间内符合条件的数值个数为多少」的一般形式，通常我们需要实现一个查询 [ 0 , x ] [0, x] [0,x] 有多少合法数值的函数 int dp(int x)，然后应用「容斥原理」求解出 [ a , b ] [a, b] [a,b] 的个数： d p ( b ) − d p ( a − 1 ) dp(b) - dp(a - 1) dp(b)−dp(a−1)。
对于本题，虽然只需要求解 [ 0 , n ] [0, n] [0,n] 范围内数的个数，但其实拓展到求 [ a , b ] [a, b] [a,b] 区间个数的也不会增加难度。

具体的，对于「数位 DP」问题通常是「从高位到低位」的分情况讨论。

不失一般性的考虑数值 n n n 的某一位 c u r cur cur 是如何被处理的：

1. 如果当前位 c u r = 1 cur = 1 cur=1 的话，由于我们需要满足「小于等于 n n n」的要求，因此如果该位填 0 0 0 的话，后面的低位填什么都是满足要求的，因此我们期望能够查表得出「长度为 i + 1 i + 1 i+1，且二进制位置 i i i 数值为 0 0 0 时」有多少合法数值，将其累加到答案中；
   与此同时，我们需要确保当前位选 1 1 1 是合法的，即我们需要记录上一位 p r e v prev prev 是什么，确保 c u r cur cur 和 p r e v prev prev 不同时为 1 1 1。
2. 如果当前位 c u r = 0 cur = 0 cur=0 的话，我们只能选 0 0 0，并决策下一位。

当出现「当前位无法填入 c u r cur cur」或者「决策到最低位」时，则完成了所有合法答案的统计。

至于流程 1 1 1 中的查表操作，我们可以使用 static 预处理出 f 数组，定义 f [ i ] [ j ] f[i][j] f[i][j] 为考虑二进制长度为 i i i，且最高位为 j j j（ 0 0 0 or 1 1 1）时的合法数个数。

注意：为了防止重复计数问题，我们在不失一般性的计算 f [ i ] [ 0 ] f[i][0] f[i][0] 和 f [ i ] [ 1 ] f[i][1] f[i][1] 时，不能采用诸如 f [ i ] [ c u r ] + = f [ i − 1 ] [ p r e v ] f[i][cur] += f[i - 1][prev] f[i][cur]+=f[i−1][prev] 的 “后向查找依赖” 的方式进行转移，而要采用 f [ i + 1 ] [ c u r ] + = f [ i ] [ p r e v ] f[i + 1][cur] += f[i][prev] f[i+1][cur]+=f[i][prev] “前向主动更新” 的方式进行转移。

不失一般性的考虑 f [ i ] [ 0 ] f[i][0] f[i][0] 和 f [ i ] [ 1 ] f[i][1] f[i][1] 能够更新哪些状态：

• 如果期望当前位填 0 0 0 的话，需要统计所有满足 ( 0… ) 2 (0…)_2 (0…)2​ 形式的合法数值，当前位的低一位只能填 1 1 1（填 0 0 0 会出现重复计数，即需要忽略前导零的数值），此时有： f [ i + 1 ] [ 0 ] = f [ i ] [ 1 ] f[i + 1][0] = f[i][1] f[i+1][0]=f[i][1]；

• 如果期望当前位填 1 1 1 的话，需要统计所有满足 ( 1… ) 2 (1…)_2 (1…)2​ 和 ( 0… ) 2 (0…)_2 (0…)2​ 形式的合法数值：

• ( 1… ) 2 (1…)_2 (1…)2​ 时，当前位的低一位只能填 0 0 0；此时有： f [ i + 1 ] [ 1 ] + = f [ i ] [ 0 ] f[i + 1][1] += f[i][0] f[i+1][1]+=f[i][0]； * ( 0… ) 2 (0…)_2 (0…)2​ 时，当前位的低一位只能填 1 1 1；此时有： f [ i + 1 ] [ 1 ] + = f [ i ] [ 1 ] f[i + 1][1] += f[i][1] f[i+1][1]+=f[i][1]。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    int findIntegers(int n) {
        if(!n) return 1;
        int N = 32;
        int dp[N][2];
        memset(dp,0,sizeof(int)*N*2);
        dp[1][0] = 1;
        dp[1][1] = 2;
        for(int i=1;i<N-1;++i){
            dp[i+1][0] = dp[i][1];
            dp[i+1][1] = dp[i][0]+dp[i][1];
        }
        int pre = 0,ans=0,idx=31;
        for(;idx>=0;--idx){
            if(((n>>idx)&1)==1) break;
        }
        for(;idx>=0;--idx){
            int cur = (n>>idx)&1;
            if(cur==1) ans+=dp[idx+1][0];
            if(pre==1&&cur==1) break;
            pre=cur;
            if(idx==0) ans++;
        }
        return ans;
    }
};

题目

假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

答案保证在 32 位有符号整数范围内。

示例 1：

输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释： 由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。

示例 2：

输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6

提示：

• 1 <= k <= 105
• 0 <= w <= 109
• n == profits.length
• n == capital.length
• 1 <= n <= 105
• 0 <= profits[i] <= 104
• 0 <= capital[i] <= 109

  思路

• 银行家算法*
  将capital和profits配对，并按照captial从小到大进行排序。
  每次对比w和capitali，如果w比capitali大，则将对应的profitsi加入到优先队列中。
  全部加完后，从优先队列中选择最大的profits加到w中。
  重复上述k次。

  代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

  class Solution { public: int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) { int n = profits.size(); vector<pair<int,int>> arr(n); priority_queue<int,vector<int>,less<int>> pq; for(int i=0;i<n;++i){ arr[i] = {capital[i],profits[i]}; } int idx = 0; sort(arr.begin(),arr.end()); for(int i=0;i<k;++i){ while(idx<n&&arr[idx].first<=w){ pq.push(arr[idx++].second); } if(!pq.empty()){ w+=pq.top(); pq.pop(); }else{ break; } } return w; } }

题目

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

示例 1：

输入： matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出： 13
解释： 下面是两条和最小的下降路径，用加粗+斜体标注：
[[2,1,3], [[2,1,3],
[6,5,4], [6,5,4],
[7,8,9]] [7,8,9]]

示例 2：

输入： matrix = [[-19,57],[-40,-5]]
输出： -59
解释： 下面是一条和最小的下降路径，用加粗+斜体标注：
[[-19,57],
[-40,-5]]

示例 3：

输入： matrix = [[-48]]
输出： -48

提示：

• n == matrix.length
• n == matrix[i].length
• 1 <= n <= 100
• -100 <= matrix[i][j] <= 100

  思路

1. DFS（超时）
   从上往下，遍历所有的情况。每次选择下面三支中路径和最小的加到上当前值作为从当前路径起始的路径长度。
2. 动态规划
   从下往上，依次遍历每一层每个节点作为起点到最下面的路径长度最小值。
   最后取第一行最小的即可。

   代码

3. DFS

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

   class Solution { public: int minFallingPathSum(vector<vector<int>>& matrix) { if(matrix.size()<1) return 0; int val = INT_MAX; for(int i=0;i<matrix[0].size();i++){ val = min(val,minFallingPathSum(matrix,0,i)); } return val; } int minFallingPathSum(vector<vector<int>>& m,int y,int x){ if(y>=m.size()) return 0; if(x<0||x>=m[0].size()) return INT_MAX; int a = minFallingPathSum(m,y+1,x-1); int c = minFallingPathSum(m,y+1,x); int b = minFallingPathSum(m,y+1,x+1); int g = min(a,min(b,c)); if(g==INT_MAX) return INT_MAX; return g+m[y][x]; } };

4. 动态规划

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

   class Solution { public: int minFallingPathSum(vector<vector<int>>& matrix) { int m = matrix.size(),n=matrix[0].size(); vector<vector<int>> dp(m,vector<int>(n,0)); for(int x=0;x<n;++x) dp[m-1][x] = matrix[m-1][x]; for(int y=m-2;y>=0;--y){ for(int x=1;x<n-1;++x){ int val = dp[y+1][x]; if(x-1>=0) val = min(val,dp[y+1][x-1]); if(x+1<n) val = min(val,dp[y+1][x+1]); dp[y][x] = matrix[y][x]+val; } } int res = INT_MAX; for(int x=0;x<n;++x) res = min(res,dp[0][x]); return res; } };

题目

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

思路

动态规划入门：

dp[i]=max(dp[i-1],nums[i]+dp[i-2])

代码

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    int rob(vector<int>& nums) {
        vector<int> dp(nums.size()+2,0);
        for(int i=0;i<nums.size();i++){
            dp[i+2] = max(nums[i] + dp[i],dp[i+1]);
        }
        return dp.back();
    }
};

题目

233. 数字 1 的个数 - 力扣（LeetCode） (leetcode-cn.com)

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：

1
2

输入：n = 13
输出：6

示例 2：

1
2

输入：n = 0
输出：0

提示：

• 0 <= n <= 2 * 10^9

思路

是一个递推的问题。

方法一：直接递推

假设输入为 a*10^n^+b

中间情况：

只要递归：$$ f( a*10^n+b ) = f(b) + f ( a * 10^n-1 ) $$即可。

边界条件：

$$ f(x)=\left{ \begin {aligned} & 0,x<1\&1,1<=x<10 } \end {aligned} \right. $$

本方法会超时

方法二：避免重复计算

在
$$a*10^n+b$$
中，

• 如果a>2，在计算完b之后，需要计算a*10^n^-1。

  容易发现：

  当a>2 的时候，在2~a之间由于最高位都不是1，因此都是计算10^n-1^，可以合并为计算一次10^n-1^，之后乘上a-2 倍。

  当a==2的时候，计算2*10^n-1^，即计算与$$a*10^n+b$$ 相同位数，不过最高为是1时候的总的1的个数。

  计算a-2个b可以合并为计算一个b之后乘上a-2，之后在计算2*10^n-1^即可。

• 如果a==1：

  数字为$$10^n+b$$ ，首先有b+1个数字至少包含一个1，也就是不小于$$10^n$$的部分最高位包含1的个数，之后递归计算b，算出来不小于10^n^部分包含的所有的1，在计算10^n^-1内的1的个数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int countDigitOne(int n) {
        if(n<1) return 0;
        if(n<10) return 1;
        int a = n,e=1;
        while(a/10){
            a/=10;
            e*=10;
        }
        int b = n - a*e;
        if(a==1) return b+1+countDigitOne(b)+countDigitOne(e-1);
        return countDigitOne(b)+countDigitOne(2*e-1)+(a-2)*countDigitOne(e-1);
    }
};

题目

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

输入: [3,2,3,null,3,null,1]

 3
/ \\
2   3
\   \
 3   1

输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

思路

dp真的不会啊，用了层次遍历。为了防止TLE用一个unordered_map来存储已经遍历过的节点,如果直接存在就使用，不存在则将当前的node算出以其为root的最大值，加入到map中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    unordered_map<TreeNode*,int> m;
    inline int get(TreeNode* node){
        if(node==NULL) return 0;
        if(m.find(node)!=m.end()){
            return m[node];
        }
        m[node]=rob(node);
        return m[node];
    }
    int rob(TreeNode* root) {
        if(root==NULL) return 0;
        m[root]=max(get(root->left)+get(root->right),
        root->val+
        (root->left==NULL?0:get(root->left->left)+get(root->left->right))+
        (root->right==NULL?0:get(root->right->left)+get(root->right->right)));
        return m[root];
    }
};

题目

516. 最长回文子序列 - 力扣（LeetCode） (leetcode-cn.com)

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列.

实例1:

输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。

示例 2：

输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

思路

• 马拉车

  马拉车算法用来解决最长回文字串的问题是最先想到的思路，但是本地比较特殊的一点在于，可以删除。如果分别删除，复杂度会太大，因此排除使用马拉车算法的思路。

• 动态规划

  设置数组dp，dp[i][j]代表从s[i] 到s[j] 的最长回文字串长度。

  初始状态： dp[i][i]=1

  中间状态：对于任意i,j 0<=i<j<n，其中任意字串的长度都已经通过循环获得。这里让j从0开始循环的，因此0~j-1内的所有字串的最大回文长度都已经知道，从0~j相当于在此基础上在最后一位上加上了s[j]。令i从j-1开始向0 循环，这样整体的长度才是从小往大：

  • 如果s[i]==s[j]，那么就是i+1~j-1内最大的回文字串长度加上2：

    dp[i][j]=dp[i+1][j-1]+2 如果`s[i]==s[j]`但是`dp[i+1][j-1]`并不是从`i+1`开始到`j-1`结束的回文字串呢？没有关系，中间的可以都删除，因此只需要保存最长的长度即可。

• 如果s[i]!=s[j]，那么只需要dp[i][j]设置为i~j-1和i+1~j中的最长回文字串长度即可：

  dp[i][j]=max(dp[i][j-1],dp[i+1][j])

由于是从头往后开始遍历的，因此遍历到i的时候再将dp[i][j]设置为1即可。

结果： dp[i][j]代表从s[i] 到s[j] 的最长回文字串长度。因此s从0到n-1的最长回文字串长度就是dp[0][n-1]。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        int dp[n][n];
        memset(dp,0,sizeof(int)*n*n);
        for(int i=0;i<n;i++){
            dp[i][i] = 1;
            for(int j=i-1;j>=0;j--){
                if(s[i]==s[j]){
                    dp[j][i] = dp[j+1][i-1]+2;
                }else{
                    dp[j][i] = max(dp[j][i-1],dp[j+1][i]);
                }
            }
        }
        return dp[0][n-1];
    }
};