1动态规划问题先找初始值然后找状态方程
2.编写函数twoSum()判断行列的位数和
3.初始值:dp[0] [1]=true
3用二维数组dp[i] [j]记录该位置机器人是否走过
4状态表达式dp[i+1] [j+1]=dp[i] [j+1]||dp[i+1] [j]判断机器人走没走到前一个位置,如果走到了前一个位置且行列位数小于等于指定k时dp[i+1] [j+1]=true;
class Solution {
public:
int twoSum(int integer1, int integer2) {
int sum = 0;
while (integer1 || integer2) {
int bit1 = integer1 % 10;
int bit2 = integer2 % 10;
integer1 = integer1 / 10;
integer2 = integer2 / 10;
sum += bit1 + bit2;
}
return sum;
}
int movingCount(int m, int n, int k) {
vector>dp(m+1, vector(n+1, false));
dp[0][1] = true;
int res = 0;
for (int i = 0;i < m;i++) {
for (int j = 0;j < n;j++) {
if ((dp[i][j+1]||dp[i+1][j])&&twoSum(i, j) <= k) {
dp[i + 1][j + 1] = true;
res++;
}
}
}
return res;
}
};
滚动数组优化:因为有上述状态方程可知下一个结果至于dp[i+1] [j]和dp[i] [j+1]有关,所以将其优化为一维数组
class Solution {
public:
int twoSum(int integer1, int integer2) {
int sum = 0;
while (integer1 || integer2) {
int bit1 = integer1 % 10;
int bit2 = integer2 % 10;
integer1 = integer1 / 10;
integer2 = integer2 / 10;
sum += bit1 + bit2;
}
return sum;
}
int movingCount(int m, int n, int k) {
vectordp(n + 1, false);
dp[1] = true;
int res = 0;
for (int i = 0;i < m;i++) {
for (int j = 0;j < n;j++) {
if ((dp[j+1]||dp[j])&&twoSum(i, j) <= k) {
dp[j + 1] = true;
res++;
}
else {
dp[j + 1] = false;
}
}
}
return res;
}
};
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)