- 旋转函数
- 统计各位数字都不同的数字个数 (动规+排列组合)
- 最大整除子集
- 猜数字大小 II
- 超级丑数
- 预测赢家
- 栅栏涂色
- 丑数 II
- 粉刷房子
旋转函数
class Solution {
public:
int DP(vector& nums){
int n=nums.size();
vectordp(n,0);
int sum=0;
for(int i=0;i
sum+=nums[i];
dp[0]+=i*nums[i];
}
int res=dp[0];
//dp[i]: 第i次旋转
//0 :4 3 2 6
//1 :6 4 3 2
//2 :2 6 4 3
//3 :3 2 6 4
//4 :4 3 2 6
//5 :6 4 3 2
for(int i=1;i
//每旋转一次,相当于加上数组和，再减去n*(当前数组最后一个元素)
//当前数组最后一个元素在原数组中的下标是: (n-i%4)
dp[i]=dp[i-1]+sum-n*nums[n-i%n];
res=dp[i]>res?dp[i]:res;
}
return res;
}
int maxRotateFunction(vector& nums) {
return DP(nums);
}
};
统计各位数字都不同的数字个数 (动规+排列组合)
class Solution {
public:
int DP(int n){
if(n==0)return 1;
vectordp(n+1,0);
//dp[0]: [0~10^0)有多少个x
//dp[i]:[10^(i-1),10^i)有多少个x
dp[0]=1;//0
int w[]={9,9,8,7,6,5,4,3,2,1};
for(int i=1;i<=n;++i){
//根据排列组合 dp[i]=9*9*8...+dp[i-1];
int mul=1;
//i位数
for(int j=0;j
mul*=w[j];
}
dp[i]=dp[i-1]+mul;
}
return dp[n];
}
int countNumbersWithUniqueDigits(int n) {
return DP(n);
}
};
最大整除子集
class Solution {
public:
vectorres;
void DP(vector& nums){
//dp[i]: 以nums[i]结尾的最大的整除子集,初始化为1
//pre[i]: 以nums[i]结尾的最大的整除子集的前一个下标位置,初始化为-1
//排序数组
sort(nums.begin(),nums.end());
int n=nums.size();
vectordp(n,1);
vectorpre(n,-1);
for(int i=1;i
//求dp[i]
for(int j=i-1;j>=0;--j){//当前的整除子集是有序的，只要nums[j]可以整除nums[i]，
//且长度大于当前dp[i]，就更新dp[i]
if(nums[i]%nums[j]==0&&dp[j]+1>dp[i]){
dp[i]=dp[j]+1;
pre[i]=j;
}
}
}
int end=0;//end是最大整除子集的结尾下标
int maxSize=1;
for(int i=0;i
if(maxSize
maxSize=dp[i];
end=i;
}
}
while(end!=-1){
res.push_back(nums[end]);
end=pre[end];
}
reverse(res.begin(),res.end());
}
vector largestDivisibleSubset(vector& nums) {
DP(nums);
return res;
}
};
猜数字大小 II
class Solution {
public:
int DP(int n){
//dp[i][j]: [i,j]上猜数字,确保获胜的最小现金数
auto dp=vector>(n+1,vector(n+1,INT_MAX));
for(int i=1;i<=n;++i){
dp[i][i]=0;
}
for(int c=2;c<=n;++c){
for(int i=1,j=c;i<=n-c+1;++i,++j){
// cout< //k=i,k=j要单独算
//正确的数k k+dp[k+1][j]
//为了确保肯定获胜：应该取两种情况的最大值
dp[i][j]=min(dp[i][j],max(dp[i][k-1],dp[k+1][j])+k);
}
dp[i][j]=min(dp[i][j],dp[i+1][j]+i);
dp[i][j]=min(dp[i][j],dp[i][j-1]+j);
}
}
return dp[1][n];
}
int getMoneyAmount(int n) {
return DP(n);
}
};
超级丑数
class Solution {
public:
int nthSuperUglyNumber(int n, vector& primes) {
if(n==1)return 1;
int m=primes.size();
int index[m];
for(int i=0;i
index[i]=1;
}
int dp[n+1];
dp[1]=1;
for(int i=2;i<=n;++i){
int minVal=INT_MAX;
for(int j=0;j
if(index[j]<=n&&dp[i-1]
minVal=std::min(minVal,dp[index[j]]*primes[j]);
}
}
dp[i]=minVal;
for(int j=0;j
if(index[j]<=n&&minVal==dp[index[j]]*primes[j]){
++index[j];
}
}
}
return dp[n];
}
};
预测赢家
解题思路：
定义一个二维数组，先明确是用来干什么的，dp[i][j] 表示两个玩家在数组 i 到 j 区间内游戏能赢对方的差值（i <= j）。
假如玩家1先取左端 nums[i]，那么玩家2能赢对方的差值是dp[i+1][j] ，如果玩家1先取取右端 nums[j]，玩家2能赢对方的差值就是dp[i][j-1]，
那么 不难理解如下公式：
d p [ i ] [ j ] = m a x ( ( n u m s [ i ] − d p [ i + 1 ] [ j ] ) , ( n u m s [ j ] − d p [ i ] [ j − 1 ] ) ) ; dp[i][j] = max((nums[i] - dp[i + 1][j]), (nums[j] - dp[i][j - 1])); dp[i][j]=max((nums[i]−dp[i+1][j]),(nums[j]−dp[i][j−1]));
确定了状态转移公式之后，就要想想如何遍历。
一些同学确定的方程，却不知道该如何遍历这个遍历推算出方程的结果，我们来看一下。
首先要给dp[i][j]进行初始化，首先当i == j的时候，nums[i]就是dp[i][j]的值。
class Solution {
public:
int DP(vector& nums){
//dp[i][j]:区间[i,j]上,能赢对方的最大差值(可能为负值)
int n=nums.size();
if(n==1)return nums[0];
auto dp=vector>(n,vector(n,0));
for(int i=0;i
dp[i][i]=nums[i];
}
for(int c=1;c//每次开始的列是c
for(int r=0;r
dp[r][c+r]=max(nums[c+r]-dp[r][c+r-1],nums[r]-dp[r+1][c+r]);
}
}
return dp[0][n-1];
}
bool PredictTheWinner(vector& nums) {
return DP(nums)>=0;
}
};
栅栏涂色
class Solution {
public:
int DP(int n,int k){
//dp[i][0]:i个栅栏柱,且第i个栅栏柱与第i-1个颜色相同的方案数
//dp[i][1]:i个栅栏柱,且第i个栅栏柱与第i-1个颜色不相同的方案数
if(n==1)return k;
if(n==2)return k*k;
vector >dp(n+1,vector(2,0));
dp[1][0]=0;
dp[1][1]=k;
for(int i=2;i<=n;++i){
dp[i][0]=dp[i-1][1];
dp[i][1]=(dp[i-1][0]+dp[i-1][1])*(k-1);
}
return dp[n][0]+dp[n][1];
}
int numWays(int n, int k) {
return DP(n,k);
}
};
丑数 II
class Solution {
public:
//本题关键思路：每个丑数都是由更小的丑数要么*2,要么*3,要么*5得到的
int DP(int n){
//dp[i]: 第i个丑数
vectordp(n+1,INT_MAX);
if(n==1)return 1;
dp[1]=1;
int index2=1;//使得2*x>第i-1个丑数的
int index3=1;
int index5=1;
for(int i=2;i<=n;++i){
dp[i]=min(dp[index2]*2,min(dp[index3]*3,dp[index5]*5));
if(dp[i]==dp[index2]*2)index2++;
if(dp[i]==dp[index3]*3)index3++;
if(dp[i]==dp[index5]*5)index5++;
}
return dp[n];
}
int nthUglyNumber(int n) {
return DP(n);
}
};
粉刷房子
class Solution {
public:
int DP(vector>& costs){
int n=costs.size();
if(n==1)return min(costs[0][0],min(costs[0][1],costs[0][2]));
//dp[i][j]:0~i号房子被粉刷且用j颜色粉刷i房子的最小花费
auto dp=vector >(n,vector(3,0));
dp[0][0]=costs[0][0];
dp[0][1]=costs[0][1];
dp[0][2]=costs[0][2];
for(int i=1;i
dp[i][0]=costs[i][0]+min(dp[i-1][1],dp[i-1][2]);
dp[i][1]=costs[i][1]+min(dp[i-1][0],dp[i-1][2]);
dp[i][2]=costs[i][2]+min(dp[i-1][1],dp[i-1][0]);
}
return min(dp[n-1][0],min(dp[n-1][1],dp[n-1][2]));
}
int minCost(vector>& costs) {
return DP(costs);
}
};
