动态规划复杂度：
状态数量* 转移的计算量
- 三角形最小路径和
行就是行，左斜的可以当做列。转移到dp[i][j]就有两种方式,dp[i-1][j]和dp[i-1][j-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n=triangle.size();
int dp[n+1][n+1];
memset(dp,0x3f3f3f,sizeof(dp));
dp[1][1]=triangle[0][0];
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+triangle[i-1][j-1];
}
}
int res=0x3f3f3f;
for(int i=1;i<=n;i++){
res=min(res,dp[n][i]);
}
return res;
}
};
|
- 统计全1子矩形
数的时候首先要思路清晰，划好界限不能遗漏，我们把每个右下角为(i,j)时有多少个计算好(设为f(i,j))，然后矩阵挨个位置遍历之后求和就可以了，计算f(i,j),我们首先把要知道每一列从上到下到(i,j)有多少个连续的1，这个需要先计算出来，比较好想，简单的dp就行了，看dp那部分.
然后开始计算f(i,j)从右向左，宽度为1、2、3…分别有几种，比如图中就有12种，这个过程相当于遍历的过程记录最小值。
复杂度on3
dp[i][j]表示以第i行j列的数往上(这一列)有多少个连续的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
28
29
30
| class Solution {
public:
int numSubmat(vector<vector<int>>& mat) {
int m=mat.size();
int n=mat[0].size();
int dp[m][n];
for(int i=0;i<n;i++){
dp[0][i]=mat[0][i];
}
for(int i=1;i<m;i++){
for(int j=0;j<n;j++){
if(mat[i][j]==1)
dp[i][j]=1+dp[i-1][j];
else
dp[i][j]=0;
}
}
int res=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
int mi=dp[i][j];
for(int k=j;k>=0;k--){
mi=min(mi,dp[i][k]);
res+=mi;
}
}
}
return res;
}
};
|
优化：单调栈(https://www.bilibili.com/video/BV115411Y7wV)
- 解码方式
首先分析几个特殊的情况，之后开始dp
dp[j]对应s[0]到s[i-1]的译码总数
如果s[i]=0,前一位只能是1或2，dp[j]=dp[j-2];
如果s[i-1]'1’或者s[i-1]‘2’&&s[i]<=‘6’，这两种情况后两位可以合并或者分开译码s[i-1]和s[i]分开译码就是dp[j-1]，合并译码就是dp[j-2]
其他情况就是只能分开译码了
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 numDecodings(string s) {
if(s.length()==0) return 0;
if(s[0]=='0')return 0;
if(s.length()==1) return 1;
int dp[s.size()+1];
dp[0]=dp[1]=1;
for(int i=1,j=2;i<s.size();i++,j++)
{
if(s[i]=='0')
{
if(s[i-1]=='1'||s[i-1]=='2') dp[j]=dp[j-2];
else
return 0;
}
else
{
if(s[i-1]=='1'||s[i-1]=='2'&&s[i]<='6')
dp[j]=dp[j-1]+dp[j-2];
else
dp[j]=dp[j-1];
}
}
return dp[s.size()];
}
};
|
- 整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int integerBreak(int n) {
vector<int>dp(n+1,0);
dp[1]=1;
for(int i=2;i<=n;i++)
for(int j=i-1;j>=1;j--)
{
dp[i]=max(dp[i],dp[j]*(i-j));
dp[i]=max(dp[i],j*(i-j));
}
return dp[n];
}
};
|
357.计算各个位数不同的数字个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
if(n==0)return 1; //n=0时，数组长度为1，运行到dp[1]会指向空地址
vector<int>dp(n+1,0);
dp[0]=1;
dp[1]=10;
for(int i=2;i<=n;i++)
{
dp[i]=dp[i-1]+(dp[i-1]-dp[i-2])*(10-(i-1)); 之前的解加上新增的i位数情况，i位数是由i-1位数加上一位数，再加的一位数只有10-(i-1)种情况。
}
return dp[n];
}
};
|
以n=3为例，n=2已经计算了0-99之间不重复的数字了，我们需要判断的是100-999之间不重复的数字，那也就只能用10-99之间的不重复的数去组成三位数，而不能使用0-9之间的不重复的数，因为他们也组成不了3位数。而10-99之间不重复的数等于dp[2]-dp[1]。
当i=2时，说明之前选取的数字只有1位，那么我们只要与这一位不重复即可，所以其实有9(10-1)种情况（比如1，后面可以跟0,2,3,4,5,6,7,8,9）。当i=3时，说明之前选取的数字有2位，那么我们需要与2位不重复，所以剩余的有8（10-2）种（比如12，后面可以跟0,3,4,5,6,7,8,9）
1326.灌溉花园的最少水龙头数目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int dp[10001];
int INF= 0x3f3f3f3f;
int minTaps(int n, vector<int>& ranges) {
memset(dp,INF,sizeof(dp));
dp[0] = 0;
for(int i = 0; i < ranges.size(); i++){
int L = max(0,i-ranges[i]);
int R = min(n,i+ranges[i]);
for(int j = L; j <= R; j++){
dp[j] = min(dp[j],dp[L]+1);
}
}
return dp[n] == INF ? -1 : dp[n];
}
};
|
