在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？思路：设nums表示棋盘，记dp[i][j]表示从棋盘左上角开始到位置(i,j)所能拿到的礼物最大值，则dp[i][j]=max(dp[i-1][j],dp[i][j-1])+nums[i][j],dp[0][0] = nums[0][0],dp[m-1][n-1]是答案。代码：class Solution { public: int maxValue(vector<vector<int>>& grid) { int m = grid.size(); if(m == 0) return 0; int n = grid[0].size(); vector<vector<int>> dp(m,vector<int>

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。思路：记dp[i],表示num[0...i]的翻译方法。则有dp[i]=dp[i-1]+x*dp[i-2],x表示num[i-2...i]是否大于等于10，小于等于25。如果是，则x=1，否则x=0。dp[0]=1代码：class Solution { public: int translateNum(int num) { if(num < 0) { return 0; } if(num == 0) return 1; vector<int> nums; while(num>0) { nums.push_back(num%10); num /= 10; }

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。思路：对于两个数x和y，拼接结果有两种，xy和yx，两种结果的位数是相同的。所以可以按照从左往右逐位比较，如果某一位的数字较小，则较小数字所在数较小。比如如果xy的第i位(0<=i<xy.length)小于yx的第i位，则xy为较小的一个。对于三个数x、y、z，有xyz、xzy、yxz、yzx、zxy、zyx。还是一样的按位比较，如果第i位的数字最小，则最小数字所在数为最小数。考虑以下流程，先从x、y、z三个数中任取两个数拼接，取最小值，然后和最后一个数拼接，就拿到答案。其实这个过程就是排序。排序依据就是两个数的拼接结果，结果小的放在前面。代码：class Solution { public: string minNumber(vector<int>& nums) { sort(nums.begin(),nums.end(),[](int x,int y){return to_string(x)+to_string(y) < to_

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。思路：分析一个例子找规律，对于1234567，百位上出现1的次数，可以分成2种情况来分析，百位前面的数字1234，百位上出现1的情况为从100～199，共100个数。所以有1234*100个数。从百位数字开始到结尾的数字，对于数字567，有完整的100～199，所以有100个数。百位上1出现的次数为1234*100+100。如果数字567，不是567，而是其他，比如80，135呢？当80的时候，百位上不可能出现1，当135时，百位上1出现的次数为135-100+1次。设某个数共有m位，从右到左第i位(从0开始)1出现的次数等于，从右到左i+1~m上的数字乘以10i加上从右到左0~i位上的数字分情况的结果，记0～i位上的数字为x，如果x小于10i则结果为0，如果x大于等于10i，小于2*10i,则结果为x-10i+1,如果x大于等于2*10i,则结果为10i。用公式表示这三种情况就是min(max(n % (pow(10,i) * 1

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。思路：数组nums,记 dp[i]，表示以下标i为结尾的子数组的和的最大值，则有dp[i]=max(dp[i-1]+nums[i],nums[i])，即dp[i-1]加上当前数和当前数比较，取其中较大值为dp[i]的值。答案为max(dp[0...n-1]),n为nums的长度。因为dp[i]只和dp[i-1]有关，所以，可以使用一个变量表示dp[i-1]，另一个变量表示d[i]。代码： class Solution { public: int maxSubArray(vector<int>& nums) { int length = nums.size(); if (length == 0) { return 0; } int pre = nums[0],cur = nums[0],maxSum = nums[0]; for(int i = 1;i < lengt